Minimum Edges to Reverse to Reach a Node

Minimum Edges to Reverse to Reach a Node is a classic graph problem that hides a beautiful trick: a shortest-path question where every edge weighs either 0 or 1. That special structure unlocks a faster algorithm than Dijkstra — 0-1 BFS with a double-ended queue.

The slow way first

You could try every combination of reversals and run a search each time — hopelessly exponential. A better-but-heavier idea is to build a weighted graph and run Dijkstra with a heap: that is O(E log V).

But look closer at the weights. Every edge costs exactly 0 or 1. When weights are only 0 and 1, a heap is overkill — we can get O(V + E) instead.

The idea: model reversals as weights, then 0-1 BFS

Rebuild the graph so the cost of reaching a node is the number of reversals. For every original edge u→v:

• add u→v with weight 0 — walking along the arrow is free,
• add v→u with weight 1 — going against the arrow is one reversal.

Now "fewest reversals" is just "shortest path" in this 0/1-weighted graph. Run 0-1 BFS: keep nodes in a deque. When you relax a weight-0 edge, push the neighbor to the front; for a weight-1 edge, push it to the back. The front always holds the cheapest unsettled node, so each node is finalized correctly without a heap.

The key insight: a deque mimics a priority queue when there are only two weights. Weight-0 neighbors are as cheap as the current node, so they go to the front; weight-1 neighbors are one more, so they go to the back.

Walk through it

Step through the animation. We start at node 0 with distance 0. Forward edges 0→1 and 0→2 cost nothing, so nodes 1 and 2 get distance 0 and jump to the front of the deque. To reach node 4 we must reverse 4→2, paying 1, so it lands at the back with distance 1. The deque ordering means we always settle the cheapest node next, and we finish with dist = [0, 0, 0, 0, 1].

Pseudocode

build graph: for each edge u->v
    add u->v with weight 0
    add v->u with weight 1
dist[everything] = infinity, dist[src] = 0
deque = [src]
while deque is not empty:
    u = pop from the FRONT
    for each (v, w) in graph[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            if w == 0: push v to the FRONT
            else:      push v to the BACK
return dist

The Python solution

def min_reversals(n, edges, src):
    from collections import deque
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append((v, 0))   # walk forward: free
        graph[v].append((u, 1))   # reverse: cost 1
    dist = [float("inf")] * n
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

• We build an adjacency list where each entry is a (neighbor, weight) pair.
• Each original edge contributes two entries: the free forward edge and the cost-1 reversed edge.
• dist[src] = 0 seeds the source; every other distance starts at infinity.
• The while loop pops from the front of the deque each time.
• Lines 14-18 are the heart of 0-1 BFS: on a better distance, a weight-0 edge pushes the neighbor to the front (appendleft), a weight-1 edge pushes it to the back (append).
• Because the front always holds a minimum-distance node, no heap is needed.

Complexity

We turn a reversal-counting problem into a shortest-path problem, then exploit the 0/1 weights to drop the log factor. Each node enters the deque a small constant number of times, giving linear time.

When this pattern shows up

Practice