Problem Description

You are given a directed weighted graph with n nodes (labeled from 0 to n-1) and a list of edges. Each edge is represented as [u, v, w], meaning there's a directed edge from node u to node v with weight w.

You're also given:

• A starting node s
• An array marked containing specific nodes of interest

Your task is to find the minimum distance from the starting node s to any of the nodes in the marked array.

The problem asks you to:

1. Calculate the shortest path from node s to all reachable nodes in the graph
2. Among all the marked nodes, find which one has the smallest distance from s
3. Return this minimum distance

If none of the marked nodes can be reached from s, return -1.

Example scenario: If you start at node s and there are multiple marked nodes, you need to find which marked node is closest to s (considering the weighted paths) and return that distance. The graph is directed, so you can only travel along edges in the specified direction.

Intuition

When we need to find the shortest path from a single source node to multiple destination nodes, we can think about this problem in two ways:

1. Run a shortest path algorithm from the source to each marked node individually
2. Run a single shortest path algorithm from the source to all nodes, then check the distances to marked nodes

The second approach is more efficient. Since we're starting from a single source s and need distances to multiple potential destinations, we can compute all shortest paths from s in one go, then simply look up the distances to the marked nodes.

This naturally leads us to think about single-source shortest path algorithms. Dijkstra's algorithm is perfect for this scenario because:

• It finds the shortest paths from one source to all other nodes
• It works with weighted graphs (as long as weights are non-negative)
• We only need to run it once, regardless of how many marked nodes we have

The key insight is that instead of treating each marked node as a separate destination and solving multiple shortest path problems, we solve it once for all nodes. After getting the shortest distances from s to every node in the graph, finding the answer becomes trivial - we just need to check which marked node has the minimum distance.

The algorithm builds an adjacency matrix g[i][j] to store edge weights (using inf for non-existent edges), then applies Dijkstra's algorithm to compute dist[i] - the shortest distance from s to node i. Finally, we scan through all marked nodes and return the minimum distance found, or -1 if all marked nodes are unreachable (distance is inf).

Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The solution implements Dijkstra's algorithm to find the shortest paths from the starting node s to all other nodes. Let's walk through the implementation step by step:

1. Build the Adjacency Matrix

g = [[inf] * n for _ in range(n)]
for u, v, w in edges:
    g[u][v] = min(g[u][v], w)

We create an n × n matrix g where g[i][j] represents the weight of the edge from node i to node j. Initially, all values are set to inf (infinity). For each edge [u, v, w], we update g[u][v] with the minimum weight (handling potential duplicate edges).

2. Initialize Dijkstra's Algorithm

dist = [inf] * n
vis = [False] * n
dist[s] = 0

• dist[i] stores the shortest distance from source s to node i
• vis[i] tracks whether node i has been processed
• Set the distance to the source itself as 0

3. Main Dijkstra's Loop

for _ in range(n):
    t = -1
    for j in range(n):
        if not vis[j] and (t == -1 or dist[t] > dist[j]):
            t = j
    vis[t] = True
    for j in range(n):
        dist[j] = min(dist[j], dist[t] + g[t][j])

The algorithm runs n iterations:

• Find the unvisited node with minimum distance: We scan through all nodes to find the unvisited node t with the smallest dist[t] value
• Mark it as visited: Set vis[t] = True
• Relax edges: For all neighbors j of node t, we update dist[j] if going through t gives a shorter path: dist[j] = min(dist[j], dist[t] + g[t][j])

4. Find the Answer

ans = min(dist[i] for i in marked)
return -1 if ans >= inf else ans

After computing all shortest distances from s, we check the distances to all marked nodes and return the minimum. If this minimum is still inf (meaning no marked node is reachable), we return -1.

Time Complexity: O(n²) due to the nested loops in Dijkstra's implementation Space Complexity: O(n²) for the adjacency matrix

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• n = 4 nodes (labeled 0, 1, 2, 3)
• edges = [[0,1,2], [0,2,5], [1,2,1], [1,3,3]]
• Starting node s = 0
• Marked nodes marked = [2, 3]

Step 1: Build the Adjacency Matrix

We create a 4×4 matrix initialized with inf, then fill in the edge weights:

     0    1    2    3
0 [ inf,  2,   5,  inf]
1 [ inf, inf,  1,   3 ]
2 [ inf, inf, inf, inf]
3 [ inf, inf, inf, inf]

Step 2: Initialize Dijkstra's Algorithm

• dist = [0, inf, inf, inf] (distance from node 0 to each node)
• vis = [False, False, False, False] (no nodes visited yet)

Step 3: Run Dijkstra's Algorithm

Iteration 1:

• Find unvisited node with minimum distance: node 0 (dist=0)
• Mark node 0 as visited: vis = [True, False, False, False]
• Relax edges from node 0:
  • dist[1] = min(inf, 0 + 2) = 2
  • dist[2] = min(inf, 0 + 5) = 5
• Updated dist = [0, 2, 5, inf]

Iteration 2:

• Find unvisited node with minimum distance: node 1 (dist=2)
• Mark node 1 as visited: vis = [True, True, False, False]
• Relax edges from node 1:
  • dist[2] = min(5, 2 + 1) = 3
  • dist[3] = min(inf, 2 + 3) = 5
• Updated dist = [0, 2, 3, 5]

Iteration 3:

• Find unvisited node with minimum distance: node 2 (dist=3)
• Mark node 2 as visited: vis = [True, True, True, False]
• Relax edges from node 2: (no outgoing edges)
• dist remains [0, 2, 3, 5]

Iteration 4:

• Find unvisited node with minimum distance: node 3 (dist=5)
• Mark node 3 as visited: vis = [True, True, True, True]
• Relax edges from node 3: (no outgoing edges)
• Final dist = [0, 2, 3, 5]

Step 4: Find the Answer

• Check distances to marked nodes: marked = [2, 3]
  • Distance to node 2: dist[2] = 3
  • Distance to node 3: dist[3] = 5
• Minimum distance = min(3, 5) = 3
• Return 3

The shortest path from node 0 to any marked node is 3 (the path 0→1→2).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2)

The algorithm implements Dijkstra's shortest path algorithm using an adjacency matrix representation. The time complexity breaks down as follows:

• Building the adjacency matrix from edges: O(E) where E is the number of edges
• The main Dijkstra loop runs n iterations
• In each iteration:
  • Finding the unvisited node with minimum distance: O(n)
  • Marking the node as visited: O(1)
  • Updating distances to all neighbors: O(n)
• Total for Dijkstra: O(n) × (O(n) + O(n)) = O(n^2)
• Finding minimum distance among marked nodes: O(|marked|) which is at most O(n)

Overall time complexity: O(E + n^2 + n) = O(n^2) (since E ≤ n^2 in the worst case)

Space Complexity: O(n^2)

The space usage consists of:

• Adjacency matrix g: O(n^2) - a 2D array of size n × n
• Distance array dist: O(n)
• Visited array vis: O(n)

Overall space complexity: O(n^2 + n + n) = O(n^2)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Handling Multiple Edges Between Same Nodes

One common pitfall is forgetting to handle duplicate edges between the same pair of nodes. The graph might contain multiple edges from node u to node v with different weights.

Pitfall Example:

# Wrong approach - overwrites previous edge
for u, v, w in edges:
    graph[u][v] = w  # This overwrites any existing edge!

Solution: Always take the minimum weight when multiple edges exist:

for u, v, w in edges:
    graph[u][v] = min(graph[u][v], w)

2. Self-Loops and Node Selection in Dijkstra

When the source node is also in the marked array, failing to properly handle the distance to itself (which should be 0) can cause issues.

Pitfall Example: If s = 0 and marked = [0, 2, 3], forgetting to set distance[s] = 0 would result in all distances remaining at infinity.

Solution: Always initialize the source distance before running Dijkstra:

distance[s] = 0  # Critical initialization

3. Integer vs Float Infinity

Using integer maximum values instead of float('inf') can cause overflow issues during addition operations in the relaxation step.

Pitfall Example:

# Wrong - can cause overflow
INF = 10**9
dist[j] = min(dist[j], dist[t] + g[t][j])  # May overflow if both are large

Solution: Use float('inf') which handles arithmetic operations correctly:

graph = [[float('inf')] * n for _ in range(n)]
distance = [float('inf')] * n

4. Incorrect Node Selection Logic

The node selection step in Dijkstra must properly handle the initial case when no node has been selected yet (t = -1).

Pitfall Example:

# Wrong - doesn't handle initial selection correctly
t = 0  # Starting with 0 might select a visited node
for j in range(n):
    if not vis[j] and dist[t] > dist[j]:
        t = j

Solution: Use a sentinel value and check for it:

t = -1
for j in range(n):
    if not vis[j] and (t == -1 or dist[t] > dist[j]):
        t = j

5. Returning Wrong Value for Unreachable Nodes

Forgetting to check if the minimum distance is still infinity before returning can lead to returning infinity instead of -1.

Pitfall Example:

# Wrong - returns infinity instead of -1
return min(distance[i] for i in marked)

Solution: Check for infinity explicitly:

ans = min(distance[i] for i in marked)
return -1 if ans >= float('inf') else ans