Minimum Weighted Subgraph With the Required Paths

Minimum Weighted Subgraph With the Required Paths

What is this problem about?

The Minimum Weighted Subgraph With the Required Paths problem gives you a directed weighted graph and three special nodes: src1, src2, and dest. Find the minimum weight subgraph such that there exist paths from src1 to dest and from src2 to dest. This means finding paths from both sources that share a common "meeting point" on the way to dest. This hard coding problem requires three Dijkstra runs.

Why is this asked in interviews?

Google asks this because it requires the non-obvious insight that the optimal solution always has a "merge point" — a node where the path from src1 and the path from src2 converge before continuing to dest. By running Dijkstra from src1, src2, and from dest on the reversed graph, you can efficiently find this optimal merge point. The shortest path, graph, and heap interview pattern is fully exercised.

Algorithmic pattern used

Three Dijkstra runs.

1. Dijkstra from src1: dist1[v] = shortest path from src1 to v.
2. Dijkstra from src2: dist2[v] = shortest path from src2 to v.
3. Dijkstra from dest on the reversed graph: distDest[v] = shortest path from v to dest.

For each node v, compute dist1[v] + dist2[v] + distDest[v]. The minimum over all v is the answer. Return -1 if no valid subgraph exists.

Example explanation

Graph: src1=0, src2=1, dest=5. Edges: (0→2, 2), (1→2, 3), (2→3, 1), (2→4, 2), (3→5, 4), (4→5, 1).

• dist1 (from 0): {0:0, 2:2, 3:3, 4:4, 5:7 or via 4→5: 5}.
• dist2 (from 1): {1:0, 2:3, ...}.
• distDest (from 5 reversed): {5:0, 3:4, 4:1, 2:min(5,2)=2, ...}.
• For each node v: dist1[v]+dist2[v]+distDest[v]. Minimum gives answer.

Common mistakes candidates make

• Running only two Dijkstra passes and missing the merge point insight.
• Forgetting to reverse the graph for the third Dijkstra run.
• Not handling the case where some nodes are unreachable (infinity + anything = infinity).
• Returning 0 instead of -1 when no valid subgraph exists.

Interview preparation tip

"Two sources to one destination" problems always have a meeting point where the two paths merge. The three-Dijkstra technique — from each source forward and from the destination backward — is the canonical solution. Practice building reversed graphs (flip all edge directions) and running Dijkstra on them. This pattern generalizes to any problem involving "optimal meeting point for multiple travelers" on weighted graphs and is a recurring hard problem at Google and Meta.