2203. Minimum Weighted Subgraph With the Required Paths

Minimum Weighted Subgraph With the Required Paths (LeetCode 2203) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Shortest Path (Dijkstra's Algorithm) subpattern.

How to solve Minimum Weighted Subgraph With the Required Paths

Minimum Weighted Subgraph With the Required Paths is a Dijkstra's Algorithm for Shortest Path problem, part of Graph Traversal Patterns (DFS & BFS). Master Dijkstra's algorithm for finding shortest paths in weighted graphs with non-negative edges.

Work towards the solution in these steps:

1. Consider what the paths from src1 to dest and src2 to dest would look like in the optimal solution.
2. It can be shown that in an optimal solution, the two paths from src1 and src2 will coincide at one node, and the remaining part to dest will be the same for both paths. Now consider how to find the node where the paths will coincide.
3. How can algorithms for finding the shortest path between two nodes help us?

The reference solution runs in O((n + m) * log n) time and O(n + m) space.

The Minimum Weighted Subgraph With the Required Paths solution and editorial walks through the full approach with reference code.

Problem statement

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 <= 105

- 0 <= edges.length <= 105

- edges[i].length == 3

- 0 <= fromi, toi, src1, src2, dest <= n - 1

- fromi != toi

- src1, src2, and dest are pairwise distinct.

- 1 <= weight[i] <= 105

Topics and companies

Topics: Graph, Shortest Path.

How to practise Minimum Weighted Subgraph With the Required Paths on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O((n + m) * log n) time and O(n + m) space.

Open Minimum Weighted Subgraph With the Required Paths in the code editor, or read the Minimum Weighted Subgraph With the Required Paths editorial for a worked solution with its approach and complexity analysis.

Where Minimum Weighted Subgraph With the Required Paths sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Shortest Path (Dijkstra's Algorithm) subpattern
• The full DSA patterns sheet

Problems related to Minimum Weighted Subgraph With the Required Paths

Other problems that use the same Shortest Path (Dijkstra's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

• Find the Safest Path in a Grid — Medium, same subpattern
• Minimum Obstacle Removal to Reach Corner — Hard, same subpattern
• Minimum Time to Visit a Cell In a Grid — Hard, same subpattern
• Network Delay Time — Medium, same subpattern
• Number of Ways to Arrive at Destination — Medium, same subpattern
• Path with Maximum Probability — Medium, same subpattern

Minimum Weighted Subgraph With the Required Paths FAQ