Minimum edges to reverse to make path from source to destination
Problem Statement
Given a directed graph with V vertices and E edges, find the minimum number of edges that need to be reversed so that there is a path from a given source to a given destination.
Example:
- Input:
V = 7, edges = [(0,1),(2,1),(2,3),(5,1),(4,5),(6,4),(6,3)], source = 0, destination = 6 - Output:
2(reverse edges (2,1) and (5,1) or similar)
Noob-Friendly Explanation
Imagine one-way streets in a city. You want to go from your house (source) to a restaurant (destination). Some streets point the wrong way. You can reverse a street's direction, but you want to reverse as few streets as possible to create a path from home to the restaurant.
The trick is to treat each original edge as having weight 0 (free to use) and add a reversed edge with weight 1 (costs 1 reversal). Then use 0-1 BFS (shortest path with 0 and 1 weights) to find the minimum cost path.
Approach 1: Brute Force
Intuition
Try all possible subsets of edges to reverse. For each subset, check if a path exists from source to destination. Return the smallest subset size that creates a valid path.
Algorithm
- For each subset of edges (from size 0 to E): a. Create a modified graph with the selected edges reversed. b. Run BFS/DFS to check if destination is reachable from source. c. If reachable, return the subset size.
import java.util.*;
public class MinReverseEdgesBrute {
public static int solve(int V, int[][] edges, int src, int dst) {
int E = edges.length;
for (int numReverse = 0; numReverse <= E; numReverse++) {
if (tryReverse(V, edges, src, dst, numReverse, 0, new boolean[E])) {
return numReverse;
}
}
return -1;
}
static boolean tryReverse(int V, int[][] edges, int src, int dst,
int target, int idx, boolean[] reversed) {
int count = 0;
for (boolean b : reversed) if (b) count++;
if (count == target) {
return canReach(V, edges, reversed, src, dst);
}
if (idx == edges.length) return false;
if (count > target) return false;
// Don't reverse edge idx
if (tryReverse(V, edges, src, dst, target, idx + 1, reversed)) return true;
// Reverse edge idx
reversed[idx] = true;
if (tryReverse(V, edges, src, dst, target, idx + 1, reversed)) return true;
reversed[idx] = false;
return false;
}
static boolean canReach(int V, int[][] edges, boolean[] reversed, int src, int dst) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
for (int i = 0; i < edges.length; i++) {
if (reversed[i]) {
adj.get(edges[i][1]).add(edges[i][0]);
} else {
adj.get(edges[i][0]).add(edges[i][1]);
}
}
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
queue.offer(src);
visited[src] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
if (node == dst) return true;
for (int neigh : adj.get(node)) {
if (!visited[neigh]) {
visited[neigh] = true;
queue.offer(neigh);
}
}
}
return false;
}
public static void main(String[] args) {
int V = 7;
int[][] edges = {{0,1},{2,1},{2,3},{5,1},{4,5},{6,4},{6,3}};
System.out.println("Min reversals: " + solve(V, edges, 0, 6));
}
}Complexity Analysis
- Time Complexity: O(2^E * (V + E)) - trying all subsets and running BFS for each
- Space Complexity: O(V + E) - for the graph and BFS structures
Approach 2: Optimal (0-1 BFS)
Intuition
Build a modified graph: for each original edge (u → v), add edge (u → v) with weight 0 (no reversal needed) and edge (v → u) with weight 1 (one reversal needed). Then find the shortest path from source to destination using 0-1 BFS (deque-based BFS for graphs with only 0 and 1 weights).
Algorithm
- For each edge (u, v), add (u, v, 0) and (v, u, 1) to the adjacency list.
- Use a deque: push weight-0 edges to the front, weight-1 edges to the back.
- Return
dist[destination].
import java.util.*;
public class MinReverseEdgesOptimal {
public static int solve(int V, int[][] edges, int src, int dst) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(new int[]{e[1], 0}); // original edge, cost 0
adj.get(e[1]).add(new int[]{e[0], 1}); // reversed edge, cost 1
}
// 0-1 BFS
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(src);
while (!deque.isEmpty()) {
int u = deque.pollFirst();
for (int[] edge : adj.get(u)) {
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) {
deque.offerFirst(v);
} else {
deque.offerLast(v);
}
}
}
}
return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}
public static void main(String[] args) {
int V = 7;
int[][] edges = {{0,1},{2,1},{2,3},{5,1},{4,5},{6,4},{6,3}};
System.out.println("Min reversals: " + solve(V, edges, 0, 6));
}
}Complexity Analysis
- Time Complexity: O(V + E) - each vertex and edge is processed at most once in 0-1 BFS
- Space Complexity: O(V + E) - for adjacency list, distance array, and deque