Minimum Weighted Subgraph With the Required Paths

Hard

#2007Time: O(n * (E + n log n)), where E is the number of edges and n is the number of nodes. The outer loop runs `n` times for each potential meeting point. Inside the loop, we run Dijkstra's algorithm three times, each taking O(E + n log n) time.Space: O(E + n), where E is the number of edges and n is the number of nodes. This space is used to store the adjacency list. Each call to Dijkstra's algorithm also uses O(n) space for the distance array and priority queue.

Algorithms

Shortest Path

Data structures

Graph

Prompt

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] = [from_i, to_i, weight_i] denotes that there exists a directed edge from from_i to to_i with weight weight_i.

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 <= 10⁵
0 <= edges.length <= 10⁵
edges[i].length == 3
0 <= from_i, to_i, src1, src2, dest <= n - 1
from_i != to_i
src1, src2, and dest are pairwise distinct.
1 <= weight[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach considers every node in the graph as a potential meeting point for the paths from src1 and src2 to dest. For each potential meeting point i, it calculates the shortest path distances: src1 -> i, src2 -> i, and i -> dest by running Dijkstra's algorithm separately for each path. The sum of these three distances gives the total weight of a subgraph for that specific meeting point. The minimum sum over all possible meeting points is the final answer.

Algorithm

Initialize min_weight to a very large value (infinity).
Build an adjacency list representation of the graph from the edges array.
Iterate through every node i from 0 to n-1, considering it as the potential meeting point.
For each node i:
- Run Dijkstra's algorithm starting from src1 to find the shortest path distance to i. Let this be d1.
- Run Dijkstra's algorithm starting from src2 to find the shortest path distance to i. Let this be d2.
- Run Dijkstra's algorithm starting from i to find the shortest path distance to dest. Let this be d3.
- If d1, d2, and d3 are all finite (i.e., paths exist), calculate the total weight: current_weight = d1 + d2 + d3.
- Update min_weight = min(min_weight, current_weight).
After checking all nodes i, if min_weight is still infinity, it means no such subgraph exists, so return -1. Otherwise, return min_weight.

Walkthrough

The fundamental idea is that any valid subgraph must contain a path from src1 to dest and a path from src2 to dest. These two paths must eventually meet at some node, say i, and then can share a common path to dest. The total weight of the subgraph is the sum of the weights of the path from src1 to i, the path from src2 to i, and the path from i to dest.

This brute-force method iterates through every node i in the graph and treats it as this potential meeting point. For each i, it performs three separate shortest path computations using Dijkstra's algorithm to find the required distances. The sum is then compared with the minimum weight found so far. While conceptually straightforward, this method is highly redundant, as it recalculates shortest paths from the same sources (src1, src2) many times.

1// This is a conceptual illustration and would be too slow.2public long minimumWeight_bruteForce(int n, int[][] edges, int src1, int src2, int dest) {3    List<List<int[]>> adj = new ArrayList<>();4    for (int i = 0; i < n; i++) {5        adj.add(new ArrayList<>());6    }7    for (int[] edge : edges) {8        adj.get(edge[0]).add(new int[]{edge[1], edge[2]});9    }10 11    long minWeight = Long.MAX_VALUE;12 13    for (int i = 0; i < n; i++) {14        // For each potential meeting point 'i', run Dijkstra 3 times15        long dist1 = dijkstraHelper(src1, i, n, adj);16        long dist2 = dijkstraHelper(src2, i, n, adj);17        long dist3 = dijkstraHelper(i, dest, n, adj);18 19        if (dist1 != Long.MAX_VALUE && dist2 != Long.MAX_VALUE && dist3 != Long.MAX_VALUE) {20            minWeight = Math.min(minWeight, dist1 + dist2 + dist3);21        }22    }23 24    return minWeight == Long.MAX_VALUE ? -1 : minWeight;25}26 27// Helper to find shortest path from a start to an end node28private long dijkstraHelper(int start, int end, int n, List<List<int[]>> adj) {29    long[] dist = new long[n];30    Arrays.fill(dist, Long.MAX_VALUE);31    dist[start] = 0;32    PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));33    pq.offer(new long[]{start, 0});34 35    while (!pq.isEmpty()) {36        long[] current = pq.poll();37        int u = (int) current[0];38        long d = current[1];39 40        if (u == end) return d; // Optimization: stop when destination is reached41        if (d > dist[u]) continue;42 43        for (int[] edge : adj.get(u)) {44            int v = edge[0];45            int weight = edge[1];46            if (dist[u] + weight < dist[v]) {47                dist[v] = dist[u] + weight;48                pq.offer(new long[]{v, dist[v]});49            }50        }51    }52    return dist[end];53}

Complexity

Time

O(n * (E + n log n)), where E is the number of edges and n is the number of nodes. The outer loop runs `n` times for each potential meeting point. Inside the loop, we run Dijkstra's algorithm three times, each taking O(E + n log n) time.

Space

O(E + n), where E is the number of edges and n is the number of nodes. This space is used to store the adjacency list. Each call to Dijkstra's algorithm also uses O(n) space for the distance array and priority queue.

Trade-offs

Pros

Conceptually simple and easy to understand the logic of a meeting point.

Cons

Extremely inefficient due to repeated computations.
The time complexity of O(n * (E + n log n)) is too high for the given constraints and will result in a 'Time Limit Exceeded' error on larger test cases.

This efficient approach solves the problem by pre-calculating all necessary shortest path distances with just three runs of Dijkstra's algorithm. It identifies that the problem can be solved by finding a common meeting node i that minimizes the sum of three path lengths: src1 -> i, src2 -> i, and i -> dest. The key optimization is to calculate the i -> dest distances for all i simultaneously by running Dijkstra once from dest on a reversed version of the graph.

Algorithm

Create an adjacency list adj for the original graph and revAdj for the graph with all edge directions reversed.
Run Dijkstra's algorithm starting from src1 on the adj graph to compute the shortest distances from src1 to all other nodes. Store this in an array dist1.
Run Dijkstra's algorithm starting from src2 on the adj graph to compute the shortest distances from src2 to all other nodes. Store this in an array dist2.
Run Dijkstra's algorithm starting from dest on the revAdj graph. This computes the shortest distances from dest to all other nodes in the reversed graph, which is equivalent to finding the shortest distances from all nodes to dest in the original graph. Store this in an array distDest.
Initialize min_weight to infinity.
Iterate through every node i from 0 to n-1:
- If dist1[i], dist2[i], and distDest[i] are all finite, calculate current_weight = dist1[i] + dist2[i] + distDest[i].
- Update min_weight = min(min_weight, current_weight).
If min_weight is still infinity, return -1. Otherwise, return min_weight.

Walkthrough

The optimal solution is based on the same meeting point logic as the brute-force approach but avoids redundant computations. The total weight for any meeting point i is dist(src1, i) + dist(src2, i) + dist(i, dest). Instead of re-running Dijkstra for each i, we can compute these distances for all i at once.

dist(src1, i) for all i: This is a standard single-source shortest path problem. We run Dijkstra starting from src1 on the original graph. This gives us an array, dist1, where dist1[i] is the shortest distance from src1 to i.
dist(src2, i) for all i: Similarly, we run Dijkstra starting from src2 on the original graph to get an array dist2.
dist(i, dest) for all i: Calculating the shortest path from every node i to a single dest is a multi-source shortest path problem. This can be efficiently solved by reversing all the edges of the graph and running a single-source shortest path algorithm from dest. The distance from dest to i in the reversed graph is the same as the distance from i to dest in the original graph. We run Dijkstra from dest on this reversed graph to get an array distDest.

After these three Dijkstra runs, we have all the necessary components. We iterate through all nodes i from 0 to n-1, find the sum dist1[i] + dist2[i] + distDest[i], and determine the minimum possible value.

1class Solution {2    public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {3        // Build adjacency lists for original and reversed graphs4        List<List<long[]>> adj = new ArrayList<>();5        List<List<long[]>> revAdj = new ArrayList<>();6        for (int i = 0; i < n; i++) {7            adj.add(new ArrayList<>());8            revAdj.add(new ArrayList<>());9        }10        for (int[] edge : edges) {11            int u = edge[0];12            int v = edge[1];13            int w = edge[2];14            adj.get(u).add(new long[]{v, w});15            revAdj.get(v).add(new long[]{u, w});16        }17 18        // Run Dijkstra from src1, src2, and dest (on reversed graph)19        long[] dist1 = dijkstra(src1, n, adj);20        long[] dist2 = dijkstra(src2, n, adj);21        long[] distDest = dijkstra(dest, n, revAdj);22 23        long minWeight = Long.MAX_VALUE;24 25        // Find the meeting point that minimizes the total weight26        for (int i = 0; i < n; i++) {27            if (dist1[i] != Long.MAX_VALUE && dist2[i] != Long.MAX_VALUE && distDest[i] != Long.MAX_VALUE) {28                long currentWeight = dist1[i] + dist2[i] + distDest[i];29                minWeight = Math.min(minWeight, currentWeight);30            }31        }32 33        return minWeight == Long.MAX_VALUE ? -1 : minWeight;34    }35 36    // Dijkstra's algorithm to find shortest paths from a single source37    private long[] dijkstra(int start, int n, List<List<long[]>> graph) {38        long[] dist = new long[n];39        Arrays.fill(dist, Long.MAX_VALUE);40        dist[start] = 0;41 42        // Priority queue stores {node, distance}43        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));44        pq.offer(new long[]{start, 0});45 46        while (!pq.isEmpty()) {47            long[] current = pq.poll();48            int u = (int) current[0];49            long d = current[1];50 51            if (d > dist[u]) {52                continue;53            }54 55            for (long[] edge : graph.get(u)) {56                int v = (int) edge[0];57                long weight = edge[1];58                if (dist[u] + weight < dist[v]) {59                    dist[v] = dist[u] + weight;60                    pq.offer(new long[]{v, dist[v]});61                }62            }63        }64        return dist;65    }66}

Complexity

Time

O(E + n log n), where E is the number of edges and n is the number of nodes. Building the graphs takes O(E + n). The main cost comes from the three runs of Dijkstra's algorithm, each taking O(E + n log n). The final loop to find the minimum weight takes O(n).

Space

O(E + n), where E is the number of edges and n is the number of nodes. This space is required to store two adjacency lists (original and reversed), three distance arrays, and the priority queue used within Dijkstra's algorithm.

Trade-offs

Pros

Highly efficient and optimal for the given constraints.
Avoids redundant computations by pre-calculating all necessary shortest paths in just three passes.

Cons

Requires the insight of using a reversed graph, which might not be immediately obvious.
Requires slightly more space to store the reversed graph's adjacency list.

Solutions

Solution

1class Solution {2private3  static final Long INF = Long.MAX_VALUE;4public5  long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {6    List<Pair<Integer, Long>>[] g = new List[n];7    List<Pair<Integer, Long>>[] rg = new List[n];8    for (int i = 0; i < n; ++i) {9      g[i] = new ArrayList<>();10      rg[i] = new ArrayList<>();11    }12    for (int[] e : edges) {13      int f = e[0], t = e[1];14      long w = e[2];15      g[f].add(new Pair<>(t, w));16      rg[t].add(new Pair<>(f, w));17    }18    long[] d1 = dijkstra(g, src1);19    long[] d2 = dijkstra(g, src2);20    long[] d3 = dijkstra(rg, dest);21    long ans = -1;22    for (int i = 0; i < n; ++i) {23      if (d1[i] == INF || d2[i] == INF || d3[i] == INF) {24        continue;25      }26      long t = d1[i] + d2[i] + d3[i];27      if (ans == -1 || ans > t) {28        ans = t;29      }30    }31    return ans;32  }33private34  long[] dijkstra(List<Pair<Integer, Long>>[] g, int u) {35    int n = g.length;36    long[] dist = new long[n];37    Arrays.fill(dist, INF);38    dist[u] = 0;39    PriorityQueue<Pair<Long, Integer>> q =40        new PriorityQueue<>(Comparator.comparingLong(Pair : : getKey));41    q.offer(new Pair<>(0L, u));42    while (!q.isEmpty()) {43      Pair<Long, Integer> p = q.poll();44      long d = p.getKey();45      u = p.getValue();46      if (d > dist[u]) {47        continue;48      }49      for (Pair<Integer, Long> e : g[u]) {50        int v = e.getKey();51        long w = e.getValue();52        if (dist[v] > dist[u] + w) {53          dist[v] = dist[u] + w;54          q.offer(new Pair<>(dist[v], v));55        }56      }57    }58    return dist;59  }60}

1class Solution:2    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int: def dijkstra(g, u): dist = [inf] * n dist[u] = 0 q = [(0, u)] while q: d, u = heappop(q) if d > dist[u]: continue for v, w in g[u]: if dist[v] > dist[u] + w: dist[v] = dist[u] + w heappush(q, (dist[v], v)) return dist g = defaultdict(list) rg = defaultdict(list) for f, t, w in edges: g[f]. append((t, w)) rg[t]. append((f, w)) d1 = dijkstra(g, src1) d2 = dijkstra(g, src2) d3 = dijkstra(rg, dest) ans = min(sum(v) for v in zip(d1, d2, d3)) return - 1 if ans >= inf else ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem