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).

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