Min Edge Reversals for Path

Problem Overview

To go from src to dst you may keep an edge as written or flip it.

Intuition

To go from src to dst you may keep an edge as written or flip it. Keeping costs nothing and flipping costs one, so the fewest flips is a shortest path on a graph whose edges only weigh 0 or 1.

Algorithm

1For every original directed edge u to v, add u to v with weight 0 and v to u with weight 1.
2Run 0-1 BFS from src using a deque.
3When relaxing a neighbor with weight 0, push it to the front; with weight 1, push it to the back.
4If dst is reached, return its distance.
5If the deque empties first, return -1.

Example Walkthrough

Input: edges force one reverse on the only route from src to dst

1. Forward edges stay free to traverse.
2. The missing forward hop is taken as a reverse of cost 1.
3. 0-1 BFS reports distance 1.

Output: 1

Common Pitfalls

• Do not use a general Dijkstra heap; 0-1 BFS is enough and faster.
• Nodes may be 1-indexed up to n; size arrays accordingly.
• Unreachable destinations must return -1, not a sentinel distance.
• Pushing the wrong end of the deque breaks the nondecreasing distance order.

Min Edge Reversals for Path.java

Java

// Approach: Model each directed edge u->v as cost 0, and the reverse v->u as
// cost 1. Minimum reversals from src to dst is then shortest path with only
// 0/1 weights, solved by 0-1 BFS (deque: 0-cost to front, 1-cost to back).
// Complexity: O(n + m) time and space.
import java.util.*;

class Solution {
    public int minimumEdgeReversal(int[][] edges, int n, int src, int dst) {
        List<int[]>[] adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++)
            adj[i] = new ArrayList<>();

        for (int[] e : edges) {
            int u = e[0], v = e[1];
            adj[u].add(new int[] { v, 0 });
            adj[v].add(new int[] { u, 1 });
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        ArrayDeque<Integer> dq = new ArrayDeque<>();
        dq.add(src);

        while (!dq.isEmpty()) {
            int u = dq.pollFirst();
            if (u == dst)
                return dist[u];

            for (int[] edge : adj[u]) {
                int v = edge[0], w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    if (w == 0)
                        dq.addFirst(v);
                    else
                        dq.addLast(v);
                }
            }
        }

        return -1;
    }
}

Was this solution helpful?