Minimum edges to reverse to make a path from source to destination

Medium

Problem

In a directed graph, return the minimum number of edges whose direction must be reversed so that a path exists from source to destination.

Example 1

Input:  edges 0→1, 2→1, 2→3, 5→1, 4→5, 6→4, 6→3, src = 0, dst = 6
Output: 2

0 → 1 → 2 (reverse 2→1) → 3 → 6 (reverse 6→3).

Also asked as: Minimum edges to reverse o make path from source to destination · Find if there is a path of more thank length from a source

Test cases

Case 1

Input:    7, [[0,1],[2,1],[2,3],[5,1],[4,5],[6,4],[6,3]], 0, 6
Expected: 2

Case 2

Input:    2, [[1,0]], 0, 1
Expected: 1

Case 3

Input:    2, [[0,1]], 0, 1
Expected: 0

Case 4

Input:    3, [[0,1]], 0, 2
Expected: -1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. 0-1 BFS on a doubled graph

Time O(V + E)Space O(V + E)

Keep every original edge with weight 0 and add its reverse with weight 1. The shortest path (0-1 BFS with a deque) from src to dst is the minimum reversals.

function minReversals(n, edges, src, dst) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) { adj[u].push([v, 0]); adj[v].push([u, 1]); }
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
const dq = [src];
while (dq.length) {
const u = dq.shift();
for (const [v, w] of adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
w === 0 ? dq.unshift(v) : dq.push(v);
}
}
}
return dist[dst] === Infinity ? -1 : dist[dst];
}

"Path of length > k from a source" (sum of edge weights, no revisits) is NP-hard in general — solved by backtracking / DFS with a visited set for small graphs.