Minimum edges to reverse to make a path from source to destination
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
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.