2203. Minimum Weighted Subgraph With the Required Paths

Problem Description

The given LeetCode problem presents a scenario where you have a weighted directed graph with n nodes numbered from 0 to n - 1. The connections between nodes are given by a list of edges, where each edge is represented by a triplet [from, to, weight], indicating a directed edge from node from to node to with a given weight.

Alongside this graph, you're provided with three distinct nodes: src1, src2, and dest. The goal is to find the minimum weight of a subgraph that allows both src1 and src2 to reach the node dest. If no such subgraph exists that allows this, then the result should be -1.

The problem is akin to finding the shortest paths in a directed graph, but with the added complexity of needing to ensure that two distinct source nodes can reach a common destination while minimizing the total weight of the paths used.

Intuition

To solve this problem, we can use Dijkstra's algorithm to find the shortest path from each source node (src1 and src2) to dest. Dijkstra's algorithm is a classic algorithm for finding the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights.

The solution takes advantage of a modified version of Dijkstra's algorithm. Normally, Dijkstra's algorithm is used to compute the shortest paths from a single source to all other nodes. However, our problem requires shortest paths from two sources src1 and src2 to one destination dest, and the paths must be part of some common subgraph.

The approach involves calculating three sets of shortest paths:

Shortest paths from src1 to all other nodes.
Shortest paths from src2 to all other nodes.
Shortest paths from dest to all other nodes (this requires reversing the edge directions to treat dest as a source).

Step 3's reverse graph computation is key for determining the shortest path from dest to other nodes in the original direction.

After computing the shortest path arrays, a simple linear pass can combine the paths from src1 and src2 to any intermediary node and from that intermediary node to dest (using reverse paths calculated in step 3). Adding these three path weights provides the total weight for each possible pair of paths reaching dest from each source. The minimum of these sums, if it is finite, gives us the minimum weight of the subgraph meeting the problem's criteria. If there's no subgraph where both src1 and src2 can reach dest, we return -1.

The intuition behind this triple shortest-path computation is to exploit the fact that if the optimal paths from src1 and src2 to dest share any common segment, those segments should be counted only once in the total weight of the subgraph.

Learn more about Graph and Shortest Path patterns.

Solution Approach

The solution approach to this problem involves several important steps which can be broken down into the following:

Graph Representation: The implementation uses a defaultdict from Python's collections module to represent the graph g and the reverse graph rg. The defaultdict allows for easy appending of edges without worrying about key errors. For instance, g[f].append((t, w)) adds a directed edge from f to t with weight w to the graph g.
Dijkstra's Algorithm: Dijkstra's algorithm is used to compute the shortest paths. A helper function dijkstra(g, u) is defined, which performs Dijkstra's on the graph g from the source node u. This function initializes a distance list dist with inf (infinity). This list holds the shortest distance from u to every other node. The distance from u to itself is set to 0. A priority queue q is then used to select the next node with the smallest distance, which makes the process efficient by always considering the closest non-visited node. The queue begins with the source node u.
Priority Queue: Python's heapq module is used to implement the priority queue in Dijkstra's algorithm. It ensures the selection of the minimum distance which is not yet processed. This is an efficient way to get the next node to process for the shortest paths (heappop(q) retrieves and removes the node with the smallest distance from the queue).
Computing Shortest Paths: The algorithm computes three sets of shortest paths: one from src1 to all other nodes as d1, one from src2 to all other nodes as d2, and one from dest to all other nodes using the reverse graph rg as d3. The reverse paths are necessary as we want to compute the shortest path from dest to any node efficiently, emulating a shortest path to dest.
Finding the Minimal Subgraph: Once we have the shortest paths from src1, src2, and dest to all other nodes, we iterate through all the nodes to calculate the sum of distances from src1 to an intermediary node i, from src2 to the same intermediary i, and from i to dest (using the reverse paths d3). ans = min(sum(v) for v in zip(d1, d2, d3)) goes through all these sums and finds the minimum.
Returning the Result: Finally, if the minimum found in the previous step is infinite, then there is no valid subgraph, and the function returns -1. Otherwise, the minimum value is the answer which represents the minimum weight of the subgraph where src1 and src2 can both reach dest.

In summary, the solution effectively combines graph representation, Dijkstra's algorithm, efficient data structures like heapq, and algorithmic ingenuity to tackle this path-finding problem and guarantee the minimal subgraph weight that satisfies the given conditions.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Assume we have a graph with 4 nodes 0 to 3, and our goal is to find the minimum weight of a subgraph that connects both src1 = 0 and src2 = 1 to dest = 3. The graph's edges are given by the following list: edges = [[0, 2, 1], [2, 3, 2], [1, 2, 2], [1, 3, 5]].

Following the solution approach:

Graph Representation: We represent the graph g and the reverse graph rg using defaultdict. g will consist of {0: [(2, 1)], 2: [(3, 2)], 1: [(2, 2), (3, 5)]}. For rg, we reverse the edges, resulting in {2: [(0, 1), (1, 2)], 3: [(2, 2), (1, 5)]}.
Dijkstra's Algorithm: We implement Dijkstra's algorithm to find the shortest paths from src1 = 0, src2 = 1, and dest = 3 (using rg).
- For src1 = 0, shortest paths are: d1 = [0, inf, 1, 3].
- For src2 = 1, shortest paths are: d2 = [inf, 0, 2, 5].
- For dest = 3 (using rg), shortest paths are: d3 = [3, 2, 2, 0].
Priority Queue: With Python's heapq, we maintain a min-heap to efficiently retrieve the next node with the smallest tentative distance during the execution of Dijkstra's algorithm.
Computing Shortest Paths: Using the above algorithm, we have computed the shortest paths from src1 to all other nodes stored in d1, from src2 to all others in d2, and from dest to all others in d3.
Finding the Minimal Subgraph: We iterate over all nodes to combine paths:
- For node 2 as an intermediary, the total weight would be d1[2] + d2[2] + d3[2] = 1 + 2 + 2 = 5.
- Direct paths to dest without going through node 2 would be d1[3] + d2[3] = 3 + 5 = 8, which is higher than going through node 2.
So, the minimum weight is found using node 2 as an intermediary.
Returning the Result: The minimum sum of distances considering all nodes as intermediaries is 5. Since it's finite, this is the value of the minimum weight of the subgraph that allows both src1 and src2 to reach dest.

The answer in this case is 5, which is the weight of the subgraph using paths 0-2-3 and 1-2-3 to reach dest node 3.

Solution Implementation

1from heapq import heappush, heappop
2from collections import defaultdict
3from typing import List
4
5class Solution:
6    def minimumWeight(self, n: int, edges: List[List[int]], source1: int, source2: int, destination: int) -> int:
7        # Define the infinite distance as a variable for later use
8        inf = float('inf')
9
10        # Dijkstra's Algorithm to find the shortest path from a single source to all other nodes
11        def dijkstra(graph, start):
12            dist = [inf] * n  # Initialize distances to infinite
13            dist[start] = 0   # Distance to the start node is 0
14            queue = [(0, start)]  # Priority queue for the minimum distance
15            while queue:
16                current_dist, node = heappop(queue)
17                if current_dist > dist[node]:
18                    continue
19                for neighbor, weight in graph[node]:
20                    if dist[neighbor] > dist[node] + weight:
21                        dist[neighbor] = dist[node] + weight
22                        heappush(queue, (dist[neighbor], neighbor))
23            return dist
24      
25        # Forward graph from source to destination
26        graph = defaultdict(list)
27        # Reverse graph from destination to source (for backward traversal)
28        reverse_graph = defaultdict(list)
29        # Construct both graphs
30        for from_node, to_node, weight in edges:
31            graph[from_node].append((to_node, weight))
32            reverse_graph[to_node].append((from_node, weight))
33
34        # Get the distance from source1 and source2 to all nodes, and from all nodes to the destination
35        distances_source1 = dijkstra(graph, source1)
36        distances_source2 = dijkstra(graph, source2)
37        distances_to_destination = dijkstra(reverse_graph, destination)
38
39        # Calculate the minimum total weight by considering all possible meeting points
40        answer = inf
41        for node in range(n):
42            total_weight = distances_source1[node] + distances_source2[node] + distances_to_destination[node]
43            answer = min(answer, total_weight)
44
45        # If the answer is still infinite, the destination isn't reachable from both sources, return -1
46        return -1 if answer == inf else answer
47

1import java.util.*;
2
3class Solution {
4    // Define infinity as the maximum value a long can hold.
5    private static final long INFINITY = Long.MAX_VALUE;
6
7    // The minimumWeight method is responsible for finding the minimum total weight
8    // of paths from two sources (src1 and src2) to one destination (dest).
9    public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
10        // Initialize adjacency lists for the graph (g) and the reverse graph (rg)
11        List<Pair<Integer, Long>>[] graph = new List[n];
12        List<Pair<Integer, Long>>[] reverseGraph = new List[n];
13        for (int i = 0; i < n; ++i) {
14            graph[i] = new ArrayList<>();
15            reverseGraph[i] = new ArrayList<>();
16        }
17      
18        // Populate the adjacency list for each edge in the graph.
19        for (int[] edge : edges) {
20            int from = edge[0], to = edge[1];
21            long weight = edge[2];
22            graph[from].add(new Pair<>(to, weight));
23            reverseGraph[to].add(new Pair<>(from, weight));
24        }
25      
26        // Run Dijkstra's algorithm to find shortest paths from src1 and src2
27        // in the graph (g) and from dest in the reverse graph (rg).
28        long[] distancesFromSrc1 = dijkstra(graph, src1);
29        long[] distancesFromSrc2 = dijkstra(graph, src2);
30        long[] distancesToDest = dijkstra(reverseGraph, dest);
31      
32        // Initialize answer as -1 to indicate no solution found yet.
33        long answer = -1;
34      
35        // Iterate over all nodes to find the minimum combined distances.
36        for (int i = 0; i < n; ++i) {
37            // Skip if any one of the distances is infinity.
38            if (distancesFromSrc1[i] == INFINITY || distancesFromSrc2[i] == INFINITY || distancesToDest[i] == INFINITY) {
39                continue;
40            }
41          
42            // Calculate the total distance for the current node.
43            long totalDistance = distancesFromSrc1[i] + distancesFromSrc2[i] + distancesToDest[i];
44          
45            // Update the answer if totalDistance is smaller than the current answer.
46            if (answer == -1 || answer > totalDistance) {
47                answer = totalDistance;
48            }
49        }
50      
51        // Return the minimum total weight of the paths found.
52        return answer;
53    }
54
55    // The dijkstra method implements Dijkstra's algorithm to find the shortest paths
56    // from a starting node (startNode) to all other nodes in the graph.
57    private long[] dijkstra(List<Pair<Integer, Long>>[] graph, int startNode) {
58        int n = graph.length;
59        long[] distances = new long[n];
60        Arrays.fill(distances, INFINITY); // Start with all distances set to infinity.
61        distances[startNode] = 0; // Distance to start node is zero.
62      
63        PriorityQueue<Pair<Long, Integer>> queue = new PriorityQueue<>(Comparator.comparingLong(Pair::getKey));
64        queue.offer(new Pair<>(0L, startNode)); // Add the start node to the priority queue.
65      
66        while (!queue.isEmpty()) {
67            Pair<Long, Integer> current = queue.poll();
68            long currentDistance = current.getKey();
69            int currentNode = current.getValue();
70          
71            // Skip if we have already found a shorter path to this node.
72            if (currentDistance > distances[currentNode]) {
73                continue;
74            }
75          
76            // For each neighbor, update the shortest distance found and add it to the queue.
77            for (Pair<Integer, Long> edge : graph[currentNode]) {
78                int neighbor = edge.getKey();
79                long edgeWeight = edge.getValue();
80                if (distances[neighbor] > distances[currentNode] + edgeWeight) {
81                    distances[neighbor] = distances[currentNode] + edgeWeight;
82                    queue.offer(new Pair<>(distances[neighbor], neighbor));
83                }
84            }
85        }
86      
87        // Return the array of shortest distances from the start node.
88        return distances;
89    }
90}
91

1#include <vector>
2#include <queue>
3
4// A utility class to represent a pair of values: the node and the distance.
5class Pair {
6public:
7    int node;
8    long long distance;
9
10    Pair(int n, long long dist) : node(n), distance(dist) {}
11};
12
13// A utility class to handle pair comparison within the priority queue.
14class ComparePair {
15public:
16    // The comparator for the priority queue to sort pairs based on distance.
17    bool operator()(const Pair& a, const Pair& b) {
18        return a.distance > b.distance;
19    }
20};
21
22class Solution {
23private:
24    const long long INFINITY = LLONG_MAX; // Define infinity as the maximum value a long long can hold.
25
26    // Dijkstra's algorithm to find the shortest paths from a starting node (startNode) to all other nodes in the graph.
27    std::vector<long long> dijkstra(const std::vector<std::vector<Pair>>& graph, int startNode) {
28        int n = graph.size();
29        std::vector<long long> distances(n, INFINITY);
30        distances[startNode] = 0; // Distance to the start node is zero.
31
32        std::priority_queue<Pair, std::vector<Pair>, ComparePair> queue;
33        queue.push(Pair(startNode, 0));
34
35        while (!queue.empty()) {
36            Pair current = queue.top();
37            queue.pop();
38
39            if (current.distance > distances[current.node]) continue;
40
41            for (const Pair& edge : graph[current.node]) {
42                int neighbor = edge.node;
43                long long edgeWeight = edge.distance;
44                if (distances[neighbor] > distances[current.node] + edgeWeight) {
45                    distances[neighbor] = distances[current.node] + edgeWeight;
46                    queue.push(Pair(neighbor, distances[neighbor]));
47                }
48            }
49        }
50
51        return distances;
52    }
53
54public:
55    long long minimumWeight(int n, std::vector<std::vector<int>>& edges, int src1, int src2, int dest) {
56        // Initialize adjacency lists for the graph and the reverse graph
57        std::vector<std::vector<Pair>> graph(n);
58        std::vector<std::vector<Pair>> reverseGraph(n);
59
60        for (const auto& edge : edges) {
61            int from = edge[0], to = edge[1];
62            long long weight = static_cast<long long>(edge[2]);
63            graph[from].push_back(Pair(to, weight));
64            reverseGraph[to].push_back(Pair(from, weight));
65        }
66
67        // Shortest paths from sources to all nodes
68        std::vector<long long> distancesFromSrc1 = dijkstra(graph, src1);
69        std::vector<long long> distancesFromSrc2 = dijkstra(graph, src2);
70        // Shortest paths from all nodes to the destination
71        std::vector<long long> distancesToDest = dijkstra(reverseGraph, dest);
72
73        long long answer = -1;
74
75        // Iterate over all nodes to find the minimum combined distances
76        for (int i = 0; i < n; ++i) {
77            if (distancesFromSrc1[i] == INFINITY || distancesFromSrc2[i] == INFINITY || distancesToDest[i] == INFINITY) {
78                continue;
79            }
80
81            long long totalDistance = distancesFromSrc1[i] + distancesFromSrc2[i] + distancesToDest[i];
82
83            if (answer == -1 || answer > totalDistance) {
84                answer = totalDistance;
85            }
86        }
87
88        return answer;
89    }
90};
91

1type Pair = {
2  first: number;
3  second: number;
4};
5
6const INFINITY: number = Number.MAX_SAFE_INTEGER; // Define infinity as the maximum safe value a number can hold in JS/TS.
7
8// The minimumWeight function is responsible for finding the minimum total weight
9// of paths from two sources (src1 and src2) to one destination (dest).
10function minimumWeight(n: number, edges: number[][], src1: number, src2: number, dest: number): number {
11  // Initialize adjacency lists for the graph and the reverse graph
12  let graph: Pair[][] = new Array(n);
13  let reverseGraph: Pair[][] = new Array(n);
14  for (let i = 0; i < n; ++i) {
15    graph[i] = [];
16    reverseGraph[i] = [];
17  }
18
19  // Populate the adjacency list for each edge in the graph.
20  edges.forEach((edge) => {
21    const [from, to, weight] = edge;
22    graph[from].push({ first: to, second: weight });
23    reverseGraph[to].push({ first: from, second: weight });
24  });
25
26  // Run Dijkstra's algorithm to find shortest paths from src1 and src2
27  // in the graph and from dest in the reverse graph.
28  let distancesFromSrc1: number[] = dijkstra(graph, src1);
29  let distancesFromSrc2: number[] = dijkstra(graph, src2);
30  let distancesToDest: number[] = dijkstra(reverseGraph, dest);
31
32  // Initialize answer as -1 to indicate no solution found yet.
33  let answer: number = -1;
34
35  // Iterate over all nodes to find the minimum combined distances.
36  for (let i = 0; i < n; ++i) {
37    // Skip if any one of the distances is infinity.
38    if (distancesFromSrc1[i] === INFINITY || distancesFromSrc2[i] === INFINITY || distancesToDest[i] === INFINITY) {
39      continue;
40    }
41  
42    // Calculate the total distance for the current node.
43    let totalDistance: number = distancesFromSrc1[i] + distancesFromSrc2[i] + distancesToDest[i];
44  
45    // Update the answer if totalDistance is smaller than the current answer.
46    if (answer === -1 || answer > totalDistance) {
47      answer = totalDistance;
48    }
49  }
50
51  // Return the minimum total weight of the paths found.
52  return answer;
53}
54
55// The dijkstra function implements Dijkstra's algorithm to find the shortest paths
56// from a starting node to all other nodes in the graph.
57function dijkstra(graph: Pair[][], startNode: number): number[] {
58  let n: number = graph.length;
59  let distances: number[] = new Array(n).fill(INFINITY); // Start with all distances set to infinity.
60  distances[startNode] = 0; // Distance to start node is zero.
61
62  let queue: Pair[] = []; // Use a queue to store nodes and distances.
63  queue.push({ first: 0, second: startNode }); // Add the start node to the priority queue.
64
65  while (queue.length > 0) {
66    // Sort and extract the node with the smallest distance
67    queue.sort((a, b) => a.first - b.first);
68    let current: Pair = queue.shift()!;
69    let currentNode: number = current.second;
70    let currentDistance: number = current.first;
71  
72    // Skip if we have already found a shorter path to this node.
73    if (currentDistance > distances[currentNode]) {
74      continue;
75    }
76  
77    // For each neighbor, update the shortest distance found and add it to the queue.
78    graph[currentNode].forEach((edge: Pair) => {
79      let neighbor: number = edge.first;
80      let edgeWeight: number = edge.second;
81      let newDistance: number = distances[currentNode] + edgeWeight;
82      if (distances[neighbor] > newDistance) {
83        distances[neighbor] = newDistance;
84        queue.push({ first: newDistance, second: neighbor });
85      }
86    });
87  }
88
89  // Return the array of shortest distances from the start node.
90  return distances;
91}
92

Time and Space Complexity

Time Complexity:

The given code implements the Dijkstra's algorithm three times. The time complexity of Dijkstra's algorithm is O(E + V log V) for each call, where E is the number of edges and V is the number of vertices (nodes) in the graph. In the code, we use a priority queue to implement the algorithm efficiently.

The first call of Dijkstra's algorithm calculates the shortest paths from src1 to all other nodes.
The second call calculates the shortest paths from src2 to all other nodes.
The third call is on the reversed graph to compute the shortest paths from dest to all other nodes.

Since we are calling this algorithm three times, the time complexity will be O(3 * (E + V log V)), which simplifies to O(E + V log V) because constants are dropped in Big O notation.

Space Complexity:

The space complexity of the code is determined by the storage required for the graph representation and the auxiliary data structures used in Dijkstra's algorithm, such as the distance array and the priority queue.

Graph g and reversed graph rg use adjacency lists to store information, which require O(E) space.
For each call of Dijkstra's algorithm, a distance array of size V is created, thus 3 * O(V) for three calls.
The priority queue can hold at most V elements at any time, which contributes O(V).

Combining these, the space complexity is O(E + V), where E is the space for storing the edges and V is the space for storing the nodes and the maximum space for the priority queue.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: