You are given an integer n denoting the number of nodes of a weighted directed graph. The nodes are numbered from 0 to n - 1.
You are also given a 2D integer array edges where edges[i] = [fromi, toi, weighti] denotes that there exists a directed edge from fromi to toi with weight weighti.
Lastly, you are given three distinct integers src1, src2, and dest denoting three distinct nodes of the graph.
Return the minimum weight of a subgraph of the graph such that it is possible to reach dest from both src1 and src2 via a set of edges of this subgraph. In case such a subgraph does not exist, return -1.
A subgraph is a graph whose vertices and edges are subsets of the original graph. The weight of a subgraph is the sum of weights of its constituent edges.
Example 1:
Input: n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5 Output: 9 Explanation: The above figure represents the input graph. The blue edges represent one of the subgraphs that yield the optimal answer. Note that the subgraph [[1,0,3],[0,5,6]] also yields the optimal answer. It is not possible to get a subgraph with less weight satisfying all the constraints.
Example 2:
Input: n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2 Output: -1 Explanation: The above figure represents the input graph. It can be seen that there does not exist any path from node 1 to node 2, hence there are no subgraphs satisfying all the constraints.
Constraints:
3 <= n <= 1050 <= edges.length <= 105edges[i].length == 30 <= fromi, toi, src1, src2, dest <= n - 1fromi != toisrc1, src2, and dest are pairwise distinct.1 <= weight[i] <= 105Problem Overview: You are given a directed weighted graph with two source nodes src1 and src2, and a destination dest. The goal is to choose a subgraph with the minimum total edge weight such that both sources can reach the destination. Edges can be shared between the two paths, so the optimal solution often merges the routes at some intermediate node.
Approach 1: Dijkstra's Algorithm from Multiple Sources (O(E log V) time, O(V + E) space)
This approach runs Dijkstra three times. First compute shortest distances from src1 to every node. Then compute shortest distances from src2. Finally reverse the graph and run Dijkstra from dest to get the shortest distance from every node to the destination. For each node i, treat it as a merge point where both paths meet. The total cost becomes dist1[i] + dist2[i] + distDest[i]. The minimum over all nodes gives the optimal subgraph weight.
The key insight: both sources may share the final portion of the path to the destination. By precomputing distances from both sources and the destination, you evaluate every possible meeting node in constant time. This is the optimal solution for sparse graphs and is the standard pattern for problems involving multiple paths merging in a graph with shortest path constraints.
Approach 2: Floyd-Warshall Algorithm (O(V^3) time, O(V^2) space)
Floyd-Warshall computes all-pairs shortest paths using dynamic programming. Build a dist[i][j] matrix representing the minimum cost from node i to node j. Iterate through every node as an intermediate vertex and update distances using dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After computing the matrix, try every node k as the merge point where both sources meet before heading to the destination. The total cost becomes dist[src1][k] + dist[src2][k] + dist[k][dest].
This approach is conceptually simple because it directly provides shortest distances between every pair of nodes. However, the O(V^3) complexity makes it impractical for large graphs. It only works when the number of nodes is relatively small.
Recommended for interviews: The multi-source Dijkstra's algorithm approach is what interviewers expect. It shows you understand shortest path optimization, graph reversal, and how to reuse distance arrays efficiently. Floyd-Warshall demonstrates correctness but is rarely acceptable for large inputs due to cubic complexity.
Dijkstra's algorithm is a popular algorithm for finding shortest paths in graphs. In this approach, we start by computing the shortest paths from the two source nodes src1 and src2 to all other nodes.
Additionally, we will compute the shortest path from the destination node dest to all other nodes in the reverse direction (which effectively finds the shortest path from all nodes to dest by reversing the graph edges).
Using these three sets of paths, we can determine the minimum weight of a subgraph that meets the problem requirements by considering all intersection points of the two paths from src1 and src2 that reach dest. A viable path configuration is when both paths culminate in a reverse path to dest. The final path weight will be calculated by summing the two source-to-intersection path costs with the intersection-to-destination path cost.
We implemented Dijkstra's algorithm to compute the shortest paths for each perspective: src1 to nodes, src2 to nodes, and each node to dest by reversing the edges.
We loop over each vertex, checking if it acts as an intersection point for two paths, and if so, compute the total path cost through it. Finally, we select the minimum valid path cost.
The time complexity is O((V + E) log V) for each execution of the Dijkstra's algorithm due to the priority queue. Since it's run three times, the total is O(3(V + E) log V), which simplifies to O((V + E) log V). The space complexity is O(V + E) because of the graph and distance storage.
The Floyd-Warshall algorithm is an alternative for finding shortest paths in graphs that can quickly solve the problem comprehensively, although less efficiently when V is large since its main focus is an all-pairs shortest path.
This method considers using a 2D array to store the minimal distances between every pair of nodes. Following this, compute the subgraph path by comparing weights from src1 to all, src2 to all, and all to dest, similar in concept to our previous method but considering all possible node intersections.
This approach is feasible but will suffer from efficiency reductions unless optimizations for sparse networks are applied, due to the fundamental cubic time complexity.
The Floyd-Warshall algorithm is executed, adapting a 2D array called dist to store shortest paths among each node pair. The nodes are examined for intersection, and collectively summed path weights are considered for the answer.
Time complexity is O(V^3) due to the triply nested loops essential in Floyd-Warshall for path comparison and storage. Space complexity stands at O(V^2) due to the 2D dist array employed in the computation.
| Approach | Complexity |
|---|---|
| Dijkstra's Algorithm from Multiple Sources | The time complexity is |
| Floyd-Warshall Algorithm | Time complexity is |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra's Algorithm from Multiple Sources | O(E log V) | O(V + E) | Best for large sparse graphs; optimal solution used in interviews |
| Floyd-Warshall Algorithm | O(V^3) | O(V^2) | Small graphs where all-pairs shortest paths are needed |
Minimum Weighted Subgraph With the Required Paths | Leetcode 2203 | Dijkstra | Contest 284 | 🔥🔥 • Coding Decoded • 2,523 views views
Watch 8 more video solutions →Practice Minimum Weighted Subgraph With the Required Paths with our built-in code editor and test cases.
Practice on FleetCode