Minimum Edge Reversals for a Path Using 0-1 BFS

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

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 src to dst, where every edge has a cost of either 0 or 1.

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:

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:

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:

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.