{x}
blog image

Minimum Weighted Subgraph With the Required Paths

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

Solution Explanation for Minimum Weighted Subgraph With the Required Paths

This problem asks to find the minimum weight of a subgraph such that we can reach a destination node (dest) from two source nodes (src1 and src2). The solution uses Dijkstra's algorithm to efficiently find shortest paths in the graph.

Approach

  1. Graph Representation: The input edges is transformed into an adjacency list representation of the directed graph. We create two adjacency lists: g representing the original graph and rg representing the reversed graph (edges are flipped). The reversed graph is crucial for efficiently finding shortest paths from dest to other nodes later.

  2. Dijkstra's Algorithm: We employ Dijkstra's algorithm three times:

    • Once from src1 to all other nodes using g.
    • Once from src2 to all other nodes using g.
    • Once from dest to all other nodes using rg (this finds shortest paths to dest).

  3. Minimum Weight Calculation: For each node i, we sum the shortest path distances from src1 to i, src2 to i, and i to dest. The minimum of these sums represents the minimum weight subgraph satisfying the conditions. This is because the sum represents the total weight of edges involved in paths from src1 and src2 to dest going through node i.

  4. Handling Infeasible Cases: If any of the Dijkstra's computations result in an infinite distance (meaning a node is unreachable), we mark the result as -1.

Time and Space Complexity

  • Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices. This is dominated by the three Dijkstra's algorithm runs. Each run of Dijkstra's algorithm takes O(E log V) time using a min-heap priority queue.

  • Space Complexity: O(V + E), primarily used to store the adjacency lists (g and rg).

Code (Python and Java)

The Python and Java code implementations closely follow the approach described above. Key data structures used include:

  • defaultdict(list) (Python) or List<Pair<Integer, Long>>[] (Java) for the adjacency list graph representation. Pair is a custom class in Java to represent edges (vertex, weight).
  • heapq (Python) or PriorityQueue (Java) for efficient implementation of Dijkstra's algorithm using a min-heap.

The code efficiently finds the minimum weight subgraph by leveraging the properties of Dijkstra's algorithm and considering all possible intermediate nodes. The handling of unreachable nodes ensures correct output even in cases where the required paths do not exist.