AlgoMaster Logo

Minimum Weighted Subgraph With the Required Paths

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We have a weighted directed graph and three special nodes: src1, src2, and dest. We need to find a subgraph (a subset of edges) such that both src1 and src2 can reach dest, and the total weight of edges in this subgraph is minimized.

Both paths from src1 and src2 to dest can share edges. If both paths pass through some common node before reaching dest, the edges from that common node to dest are counted only once. The problem reduces to finding a meeting node m where both paths converge, and from m a single path continues to dest.

In other words, we want to minimize: dist(src1, m) + dist(src2, m) + dist(m, dest) over all possible meeting nodes m.

Key Constraints:

  • n <= 10^5 and edges.length <= 10^5 -> Anything worse than near-linear-with-a-log-factor per traversal is too slow. A constant number of Dijkstra runs fits; running Dijkstra once per node does not.
  • weighti >= 1 -> All weights are positive, so Dijkstra applies (no need for Bellman-Ford).
  • Up to 10^5 edges each with weight up to 10^5 means a path can sum past 10^10, beyond 32-bit int. Distances and the final answer must use 64-bit integers.
  • The graph is directed, so distances toward dest require a separate reverse graph rather than reusing the forward edges.

Approach 1: Brute Force (Dijkstra per Meeting Node)

Intuition

For every possible meeting node m, compute the shortest path from src1 to m, from src2 to m, and from m to dest. The answer is the minimum sum across all valid meeting nodes. Computing dist(src1, m) and dist(src2, m) for all m takes two Dijkstra runs, but dist(m, dest) for every m is found by running Dijkstra separately from each node, which is O(n * E log V) and too slow for n = 10^5.

Algorithm

  1. Build the adjacency list from the edges.
  2. Run Dijkstra from src1 to get dist1[v] for all v.
  3. Run Dijkstra from src2 to get dist2[v] for all v.
  4. For each node m where both dist1[m] and dist2[m] are finite, run Dijkstra from m and check dist(m, dest).
  5. Return the minimum of dist1[m] + dist2[m] + dist(m, dest) across all valid m.

Visualization and Code

Loading animation...

The next approach replaces the per-node Dijkstra runs with a single one. Computing dist(m, dest) for every m is itself a single-source shortest-path problem if the edges are reversed.

Approach 2: Three Dijkstra Runs with Reverse Graph (Optimal)

Intuition

The bottleneck in the brute force is computing dist(m, dest) for every node m. Dijkstra already computes the shortest path from one fixed source to every other node. The distance from m to dest in the original graph equals the distance from dest to m in the graph with every edge reversed. So reversing all edges and running one Dijkstra from dest on that reversed graph yields dist(m, dest) for all m at once.

With three Dijkstra runs:

  1. Dijkstra from src1 on the forward graph gives dist1[m] for all m.
  2. Dijkstra from src2 on the forward graph gives dist2[m] for all m.
  3. Dijkstra from dest on the reverse graph gives distDest[m] = shortest path from m to dest.

The answer is min(dist1[m] + dist2[m] + distDest[m]) over all nodes m.

Algorithm

  1. Build both the forward adjacency list and the reverse adjacency list from the edges.
  2. Run Dijkstra from src1 on the forward graph to get dist1[].
  3. Run Dijkstra from src2 on the forward graph to get dist2[].
  4. Run Dijkstra from dest on the reverse graph to get distDest[].
  5. For each node m from 0 to n-1, if all three distances are finite, compute dist1[m] + dist2[m] + distDest[m].
  6. Return the minimum sum, or -1 if no valid meeting node exists.

Visualization and Code

Loading animation...