Minimum Weighted Subgraph With the Required Paths — Solution
Minimum Weighted Subgraph With the Required Paths solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Weighted Subgraph With the Required Paths is a hard coding problem on graph, heap and shortest path, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Graph, Heap, Shortest Path
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A weighted directed graph has n nodes numbered 0 to n - 1. Each edges[i] = [from, to, weight] is an edge from from to to with the given positive weight; there may be several edges between the same pair of nodes.
You are also given three distinct nodes src1, src2 and dest. Choose a set of edges (a subgraph) in which dest can be reached from src1 and from src2. The weight of the subgraph is the sum of its edges' weights, each edge counted once.
Return the minimum possible weight of such a subgraph, or -1 if no subgraph works.
CodeKairo keeps every answer inside a 32-bit integer by bounding n and the weights (see the constraints).
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: Keep 1 → 0 (3), 0 → 5 (6): both sources reach 5 for a total of 9.
Example 2
Input: n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
Output: -1
Explanation: No edge leaves node 1, so `dest = 2` is unreachable from `src2`.
Example 3
Input: n = 4, edges = [[0,2,4],[1,2,4],[2,3,5],[0,3,20],[1,3,20]], src1 = 0, src2 = 1, dest = 3
Output: 13
Explanation: Both paths meet at node 2 and share the edge 2 → 3: 4 + 4 + 5 = 13.
Constraints
3 <= n <= 10^40 <= edges.length <= 10^5edges[i].length == 30 <= from, to < nfrom != to1 <= weight <= 10^40 <= src1, src2, dest < nsrc1, src2 and dest are pairwise distinct
Hints for Minimum Weighted Subgraph With the Required Paths
Hint 1
In an optimal subgraph the path from
src1and the path fromsrc2meet at some nodevand share everything fromvtodest.Hint 2
So the answer is
min over vofdist(src1, v) + dist(src2, v) + dist(v, dest)— three shortest-path tables.Hint 3
Run Dijkstra from
src1and fromsrc2on the graph, and fromdeston the graph with every edge reversed; that last run givesdist(v, dest)for allvat once.
How to solve Minimum Weighted Subgraph With the Required Paths
Two paths into the same destination can be assumed to merge once and then share the rest. If they merge at v, the cheapest such subgraph costs the shortest src1 → v, plus the shortest src2 → v, plus the shortest v → dest. Trying every v needs only three Dijkstra runs.
Approach
- Build the adjacency list and the reversed adjacency list.
- Dijkstra from
src1and fromsrc2on the graph; Dijkstra fromdeston the reversed graph. - For every node
vreached by all three runs, evaluated1[v] + d2[v] + dr[v]. - Return the minimum, or
-1if no node is reached by all three.
Why it works
Take an optimal subgraph and walk back from dest along the src1 path; the first node where it touches the src2 path is a merge point v, and from there the two can share one route. Replacing each of the three pieces by a shortest path cannot increase the weight, and the formula's value is always realisable (the union of the three paths), so the minimum over v is the answer.
Complexity
- Time —
O((n + m) log m) - Space —
O(n + m)
Pitfalls
- Edges are directed; the third search must run on the reversed graph from
dest, not forward. vmay besrc1,src2ordestitself — e.g. when one source's path passes through the other.- Use 64-bit (or a large sentinel) for unreachable distances so adding three of them cannot overflow.
Reference solution
Python
from typing import List
import heapq
def minimumWeight(n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
fwd = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for u, v, w in edges:
fwd[u].append((v, w))
rev[v].append((u, w))
INF = float("inf")
def dijkstra(adj, src):
dist = [INF] * n
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in adj[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(heap, (d + w, v))
return dist
a, b, c = dijkstra(fwd, src1), dijkstra(fwd, src2), dijkstra(rev, dest)
best = min(a[v] + b[v] + c[v] for v in range(n))
return -1 if best == INF else bestJava
static long[] dijkstra(int n, List<List<int[]>> adj, int src) {
long[] dist = new long[n];
Arrays.fill(dist, Long.MAX_VALUE);
dist[src] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
pq.add(new long[]{0, src});
while (!pq.isEmpty()) {
long[] top = pq.poll();
int u = (int) top[1];
if (top[0] > dist[u]) continue;
for (int[] e : adj.get(u)) {
long nd = top[0] + e[1];
if (nd < dist[e[0]]) { dist[e[0]] = nd; pq.add(new long[]{nd, e[0]}); }
}
}
return dist;
}
public static int minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
List<List<int[]>> fwd = new ArrayList<>(), rev = new ArrayList<>();
for (int i = 0; i < n; i++) { fwd.add(new ArrayList<>()); rev.add(new ArrayList<>()); }
for (int[] e : edges) {
fwd.get(e[0]).add(new int[]{e[1], e[2]});
rev.get(e[1]).add(new int[]{e[0], e[2]});
}
long[] a = dijkstra(n, fwd, src1), b = dijkstra(n, fwd, src2), c = dijkstra(n, rev, dest);
long best = Long.MAX_VALUE;
for (int v = 0; v < n; v++) {
if (a[v] == Long.MAX_VALUE || b[v] == Long.MAX_VALUE || c[v] == Long.MAX_VALUE) continue;
best = Math.min(best, a[v] + b[v] + c[v]);
}
return best == Long.MAX_VALUE ? -1 : (int) best;
}C++
vector<long long> dijkstraFrom(int n, vector<vector<pair<int, int>>>& adj, int src) {
const long long INF = LLONG_MAX / 4;
vector<long long> dist(n, INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
long long d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (auto& e : adj[u]) {
int v = e.first, w = e.second;
if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); }
}
}
return dist;
}
int minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
vector<vector<pair<int, int>>> fwd(n), rev(n);
for (auto& e : edges) {
fwd[e[0]].push_back({e[1], e[2]});
rev[e[1]].push_back({e[0], e[2]});
}
auto a = dijkstraFrom(n, fwd, src1), b = dijkstraFrom(n, fwd, src2), c = dijkstraFrom(n, rev, dest);
const long long INF = LLONG_MAX / 4;
long long best = INF;
for (int v = 0; v < n; v++) {
if (a[v] == INF || b[v] == INF || c[v] == INF) continue;
best = min(best, a[v] + b[v] + c[v]);
}
return best == INF ? -1 : (int) best;
}JavaScript
var minimumWeight = function(n, edges, src1, src2, dest) {
var fwd = [], rev = [];
for (var i = 0; i < n; i++) { fwd.push([]); rev.push([]); }
for (var e = 0; e < edges.length; e++) {
fwd[edges[e][0]].push(edges[e][1], edges[e][2]);
rev[edges[e][1]].push(edges[e][0], edges[e][2]);
}
var a = dijkstra(n, fwd, src1), b = dijkstra(n, fwd, src2), c = dijkstra(n, rev, dest);
var best = -1;
for (var v = 0; v < n; v++) {
if (a[v] < 0 || b[v] < 0 || c[v] < 0) continue;
var s = a[v] + b[v] + c[v];
if (best < 0 || s < best) best = s;
}
return best;
};
// Dijkstra over a heap of packed keys dist * 16384 + node (n <= 10^4).
var dijkstra = function(n, adj, src) {
var dist = [], done = [];
for (var i = 0; i < n; i++) { dist.push(-1); done.push(false); }
dist[src] = 0;
var heap = [src];
while (heap.length > 0) {
var key = heapPop(heap), u = key % 16384, d = (key - u) / 16384;
if (done[u]) continue;
done[u] = true;
var list = adj[u];
for (var j = 0; j < list.length; j += 2) {
var v = list[j], nd = d + list[j + 1];
if (!done[v] && (dist[v] < 0 || nd < dist[v])) { dist[v] = nd; heapPush(heap, nd * 16384 + v); }
}
}
return dist;
};
var heapPush = function(h, v) {
h.push(v);
var i = h.length - 1;
while (i > 0) {
var p = (i - 1) >> 1;
if (h[p] <= h[i]) break;
var t = h[p]; h[p] = h[i]; h[i] = t;
i = p;
}
};
var heapPop = function(h) {
var top = h[0];
var last = h.pop();
if (h.length > 0) {
h[0] = last;
var j = 0;
for (;;) {
var l = 2 * j + 1, r = l + 1, s = j;
if (l < h.length && h[l] < h[s]) s = l;
if (r < h.length && h[r] < h[s]) s = r;
if (s === j) break;
var t = h[s]; h[s] = h[j]; h[j] = t;
j = s;
}
}
return top;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 107 graph problems · the whole catalogue
Learn the technique: Graph Data Structure · Heaps and Priority Queues