Problem Statement
Given a directed graph with n vertices numbered from 1 to n and a list of directed edges edges[][], where each edge is represented as [u, v], we are also given a source vertex src and a destination vertex dst.
We need to find the minimum number of edges that must be reversed so that there is at least one path from src to dst.
If it is not possible to create a path from src to dst, return -1.
Example
Input
n = 3
edges = [[1, 2], [3, 2]]
src = 1
dst = 3
Output
1
Explanation
The existing edges are:
1 -> 2
3 -> 2
There is no path from 1 to 3.
If we reverse the edge:
3 -> 2
it becomes:
2 -> 3
Now we have:
1 -> 2 -> 3
Therefore, only 1 edge reversal is required.
Key Concept
The main idea is to convert the problem into a shortest path problem.
For every directed edge:
u -> v
we create two possible movements:
u -> v with cost 0
v -> u with cost 1
Why?
If we travel in the original direction u -> v, we do not need to reverse the edge, so the cost is 0.
If we travel in the opposite direction v -> u, we must reverse the edge, so the cost is 1.
Therefore, the problem becomes:
Find the minimum-cost path from
srctodst, where every edge has a cost of either0or1.
This is exactly what 0-1 BFS is designed for.
What is 0-1 BFS?
0-1 BFS is a shortest-path algorithm used when all edge weights are either:
0 or 1
It uses a Deque (Double Ended Queue) instead of a normal queue or priority queue.
When we find an edge with:
cost = 0
we add the vertex to the front of the deque.
When we find an edge with:
cost = 1
we add the vertex to the back of the deque.
This ensures that paths with smaller costs are processed first.
Building the Graph
Suppose the original graph contains:
u -> v
We add two edges to our adjacency list:
u -> v cost 0
v -> u cost 1
For example:
edges = [[1, 2]]
becomes:
1 -> 2 cost 0
2 -> 1 cost 1
The first edge represents using the edge normally.
The second edge represents reversing it.
Algorithm
We maintain a dist[] array.
dist[i] = minimum number of reversals required to reach vertex i
Initially, all distances are infinity.
The source has distance 0:
dist[src] = 0
Then we perform 0-1 BFS.
For every edge from u to v with cost cost:
newDistance = dist[u] + cost
If this value is smaller than dist[v], update it.
If cost == 0, add v to the front.
If cost == 1, add v to the back.
Finally:
dist[dst]
is our answer.
If dst is never reached, return -1.
Dry Run
Consider:
n = 3
edges = [[1, 2], [3, 2]]
src = 1
dst = 3
After converting the graph:
1 -> 2 cost 0
2 -> 1 cost 1
3 -> 2 cost 0
2 -> 3 cost 1
Initial distances:
dist[1] = 0
dist[2] = INF
dist[3] = INF
Deque:
[1]
Process vertex 1.
We have:
1 -> 2 cost 0
So:
dist[2] = 0
Because the cost is 0, add 2 to the front.
Deque:
[2]
Now process vertex 2.
We can reach 3 by using:
2 -> 3 cost 1
Therefore:
dist[3] = dist[2] + 1
= 0 + 1
= 1
So the final answer is:
1
Java Implementation
import java.util.*;
class Solution {
public int minimumEdgeReversal(int[][] edges, int n, int src, int dst) {
// Adjacency list: {neighbor, cost}
List<int[]>[] graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
}
// Build the graph
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
// Original direction - no reversal required
graph[u].add(new int[]{v, 0});
// Reverse direction - one reversal required
graph[v].add(new int[]{u, 1});
}
int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
Deque<Integer> deque = new ArrayDeque<>();
// Source requires 0 reversals
dist[src] = 0;
deque.addFirst(src);
while (!deque.isEmpty()) {
int u = deque.pollFirst();
for (int[] next : graph[u]) {
int v = next[0];
int cost = next[1];
int newDist = dist[u] + cost;
if (newDist < dist[v]) {
dist[v] = newDist;
// Process cost 0 edges first
if (cost == 0) {
deque.addFirst(v);
}
// Process cost 1 edges later
else {
deque.addLast(v);
}
}
}
}
// Destination cannot be reached
if (dist[dst] == Integer.MAX_VALUE) {
return -1;
}
return dist[dst];
}
}
Code Explanation
1. Creating the adjacency list
List<int[]>[] graph = new ArrayList[n + 1];
We use an adjacency list because the graph can contain up to 10^5 vertices and edges.
Each entry stores:
{neighbor, cost}
For example:
{2, 0}
means we can move to vertex 2 without reversing an edge.
{2, 1}
means we need one reversal.
2. Adding both directions
For every original edge:
int u = edge[0];
int v = edge[1];
we add:
graph[u].add(new int[]{v, 0});
This represents the original edge:
u -> v
No reversal is needed.
Then:
graph[v].add(new int[]{u, 1});
represents reversing the edge:
v -> u
which costs one reversal.
3. Initializing distances
int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
Initially, we assume every vertex is unreachable.
Then:
dist[src] = 0;
because we are already at the source and have not reversed any edge.
4. Using a Deque
Deque<Integer> deque = new ArrayDeque<>();
The deque allows us to insert elements from both ends.
For a zero-cost edge:
deque.addFirst(v);
For a one-cost edge:
deque.addLast(v);
This is the main idea behind 0-1 BFS.
5. Relaxing edges
For every neighboring vertex:
int newDist = dist[u] + cost;
If the new path requires fewer reversals:
if (newDist < dist[v])
we update the distance:
dist[v] = newDist;
6. Returning the answer
After processing the graph:
if (dist[dst] == Integer.MAX_VALUE) {
return -1;
}
If the destination was never reached, there is no possible path.
Otherwise:
return dist[dst];
gives the minimum number of edge reversals.
Why Not Normal BFS?
Normal BFS works when every edge has the same cost.
Here, the transformed graph contains:
0-cost edges
1-cost edges
For example:
A -> B cost 0
A -> C cost 1
Both edges represent one step, but they have different costs.
Normal BFS minimizes the number of edges, not the number of reversals.
Therefore, normal BFS is not sufficient.
Why Not Dijkstra?
Dijkstra's algorithm can solve this problem because the edge weights are non-negative.
However, all weights here are only:
0 and 1
0-1 BFS is specifically optimized for this situation and can solve the problem in:
O(n + m)
instead of the typical:
O((n + m) log n)
for a priority-queue implementation of Dijkstra.
Important Observation
The most important trick in this problem is:
Original edge:
u -> v
Convert to:
u -> v cost 0
v -> u cost 1
Once this transformation is made, the problem is no longer about explicitly reversing edges.
Instead, we simply find the shortest path where the cost represents the number of reversals.
This technique is useful in many graph problems where we need to minimize the number of changes or modifications required to follow a path.
Complexity Analysis
Let:
n = number of vertices
m = number of edges
Each original edge produces two edges in the transformed graph.
Therefore, the transformed graph contains 2m edges.
0-1 BFS processes every vertex and edge a constant number of times.
Time Complexity
O(n + m)
Auxiliary Space
O(n + m)
This satisfies the required constraints.
Edge Cases
Source and destination are the same
If:
src == dst
we are already at the destination.
Therefore, the answer is:
0
The implementation naturally handles this because:
dist[src] = 0;
and dist[dst] is also 0.
No path exists
If the destination cannot be reached even after considering reversed edges, the answer is:
-1
Path already exists
If a path from src to dst exists using only the original directions, every edge on that path has cost 0.
Therefore, the answer is:
0
Conclusion
The key to solving Minimum Edge Reversals for a Path is to convert every directed edge into two weighted edges:
u -> v : 0
v -> u : 1
Then use 0-1 BFS with a Deque to find the minimum total cost from src to dst.
The total cost represents exactly how many edges need to be reversed.
Therefore, the solution runs efficiently in:
Time: O(n + m)
Space: O(n + m)
This makes 0-1 BFS an ideal technique for minimum-cost graph problems where edge costs are restricted to 0 and 1.
Join the conversation! Your thoughts help the community grow.