Scale Engineer

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] = [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

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.

// This is a conceptual illustration and would be too slow.public long minimumWeight_bruteForce(int n, int[][] edges, int src1, int src2, int dest) {    List<List<int[]>> adj = new ArrayList<>();    for (int i = 0; i < n; i++) {        adj.add(new ArrayList<>());    }    for (int[] edge : edges) {        adj.get(edge[0]).add(new int[]{edge[1], edge[2]});    }     long minWeight = Long.MAX_VALUE;     for (int i = 0; i < n; i++) {        // For each potential meeting point 'i', run Dijkstra 3 times        long dist1 = dijkstraHelper(src1, i, n, adj);        long dist2 = dijkstraHelper(src2, i, n, adj);        long dist3 = dijkstraHelper(i, dest, n, adj);         if (dist1 != Long.MAX_VALUE && dist2 != Long.MAX_VALUE && dist3 != Long.MAX_VALUE) {            minWeight = Math.min(minWeight, dist1 + dist2 + dist3);        }    }     return minWeight == Long.MAX_VALUE ? -1 : minWeight;} // Helper to find shortest path from a start to an end nodeprivate long dijkstraHelper(int start, int end, int n, List<List<int[]>> adj) {    long[] dist = new long[n];    Arrays.fill(dist, Long.MAX_VALUE);    dist[start] = 0;    PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));    pq.offer(new long[]{start, 0});     while (!pq.isEmpty()) {        long[] current = pq.poll();        int u = (int) current[0];        long d = current[1];         if (u == end) return d; // Optimization: stop when destination is reached        if (d > dist[u]) continue;         for (int[] edge : adj.get(u)) {            int v = edge[0];            int weight = edge[1];            if (dist[u] + weight < dist[v]) {                dist[v] = dist[u] + weight;                pq.offer(new long[]{v, dist[v]});            }        }    }    return dist[end];}

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.

Solutions

class Solution {private  static final Long INF = Long.MAX_VALUE;public  long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {    List<Pair<Integer, Long>>[] g = new List[n];    List<Pair<Integer, Long>>[] rg = new List[n];    for (int i = 0; i < n; ++i) {      g[i] = new ArrayList<>();      rg[i] = new ArrayList<>();    }    for (int[] e : edges) {      int f = e[0], t = e[1];      long w = e[2];      g[f].add(new Pair<>(t, w));      rg[t].add(new Pair<>(f, w));    }    long[] d1 = dijkstra(g, src1);    long[] d2 = dijkstra(g, src2);    long[] d3 = dijkstra(rg, dest);    long ans = -1;    for (int i = 0; i < n; ++i) {      if (d1[i] == INF || d2[i] == INF || d3[i] == INF) {        continue;      }      long t = d1[i] + d2[i] + d3[i];      if (ans == -1 || ans > t) {        ans = t;      }    }    return ans;  }private  long[] dijkstra(List<Pair<Integer, Long>>[] g, int u) {    int n = g.length;    long[] dist = new long[n];    Arrays.fill(dist, INF);    dist[u] = 0;    PriorityQueue<Pair<Long, Integer>> q =        new PriorityQueue<>(Comparator.comparingLong(Pair : : getKey));    q.offer(new Pair<>(0L, u));    while (!q.isEmpty()) {      Pair<Long, Integer> p = q.poll();      long d = p.getKey();      u = p.getValue();      if (d > dist[u]) {        continue;      }      for (Pair<Integer, Long> e : g[u]) {        int v = e.getKey();        long w = e.getValue();        if (dist[v] > dist[u] + w) {          dist[v] = dist[u] + w;          q.offer(new Pair<>(dist[v], v));        }      }    }    return dist;  }}

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 →

Next problem