183. BFS Shortest Hops

Why this mechanism works

Each edge costs one, so processing all distance-d vertices before distance-(d+1) vertices makes first discovery optimal. Use FIFO order and assign a distance when enqueuing. A vertex needs no later improvement because every competing route arrives from an equal or greater depth.

State and boundaries

dist[v] is -1 until discovery, then its shortest hop count. The queue is ordered by nondecreasing assigned distance.

Protocol

1. Set start distance to zero and enqueue it.
2. Pop the next vertex.
3. Return if it is target.
4. For each undiscovered neighbor assign current distance+1 and enqueue.
5. Return -1 on exhaustion.

Visualization

0 -> 1 -> 3
 \-> 2 -> 4 -> 3
BFS layers: [0], [1,2], [3,4]
distance to 3 is 2

Python implementation

from collections import deque

def shortest_hops(adj, start, target):
    dist = [-1] * len(adj)
    dist[start] = 0
    queue = deque([start])
    while queue:
        u = queue.popleft()
        if u == target:
            return dist[u]
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                queue.append(v)
    return -1

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 shortest_hops: dist = [-1] * len(adj)
adj=[[1, 2], [3], [4], [], [3]]; start=0; target=3; dist=[-1, -1, -1, -1, -1]

L5 shortest_hops: dist[start] = 0
adj=[[1, 2], [3], [4], [], [3]]; start=0; target=3; dist=[0, -1, -1, -1, -1]

L6 shortest_hops: queue = deque([start])
adj=[[1, 2], [3], [4], [], [3]]; start=0; target=3; dist=[0, -1, -1, -1, -1]; queue=deque([0])

L8 shortest_hops: u = queue.popleft()
adj=[[1, 2], [3], [4], [], [3]]; start=0; target=3; dist=[0, -1, -1, -1, -1]; queue=deque([]); u=0

L11 shortest_hops: for v in adj[u]:
adj=[[1, 2], [3], [4], [], [3]]; start=0; target=3; dist=[0, -1, -1, -1, -1]; queue=deque([]); u=0; v=1

L13 shortest_hops: dist[v] = dist[u] + 1
adj=[[1, 2], [3], [4], [], [3]]; start=0; target=3; dist=[0, 1, -1, -1, -1]; queue=deque([]); u=0; v=1

L14 shortest_hops: queue.append(v)
adj=[[1, 2], [3], [4], [], [3]]; start=0; target=3; dist=[0, 1, -1, -1, -1]; queue=deque([1]); u=0; v=1

L11 shortest_hops: for v in adj[u]:
adj=[[1, 2], [3], [4], [], [3]]; start=0; target=3; dist=[0, 1, -1, -1, -1]; queue=deque([1]); u=0; v=2

... 7 intermediate state changes omitted ...

L11 shortest_hops: for v in adj[u]:
adj=[[1, 2], [3], [4], [], [3]]; start=0; target=3; dist=[0, 1, 1, 2, -1]; queue=deque([3]); u=2; v=4

L13 shortest_hops: dist[v] = dist[u] + 1
adj=[[1, 2], [3], [4], [], [3]]; start=0; target=3; dist=[0, 1, 1, 2, 2]; queue=deque([3]); u=2; v=4

L14 shortest_hops: queue.append(v)
adj=[[1, 2], [3], [4], [], [3]]; start=0; target=3; dist=[0, 1, 1, 2, 2]; queue=deque([3, 4]); u=2; v=4

L8 shortest_hops: u = queue.popleft()
adj=[[1, 2], [3], [4], [], [3]]; start=0; target=3; dist=[0, 1, 1, 2, 2]; queue=deque([4]); u=3; v=4

L4 shortest_hops: dist = [-1] * len(adj)
adj=[[1], [], []]; start=0; target=2; dist=[-1, -1, -1]

L5 shortest_hops: dist[start] = 0
adj=[[1], [], []]; start=0; target=2; dist=[0, -1, -1]

L6 shortest_hops: queue = deque([start])
adj=[[1], [], []]; start=0; target=2; dist=[0, -1, -1]; queue=deque([0])

L8 shortest_hops: u = queue.popleft()
adj=[[1], [], []]; start=0; target=2; dist=[0, -1, -1]; queue=deque([]); u=0

L11 shortest_hops: for v in adj[u]:
adj=[[1], [], []]; start=0; target=2; dist=[0, -1, -1]; queue=deque([]); u=0; v=1

L13 shortest_hops: dist[v] = dist[u] + 1
adj=[[1], [], []]; start=0; target=2; dist=[0, 1, -1]; queue=deque([]); u=0; v=1

L14 shortest_hops: queue.append(v)
adj=[[1], [], []]; start=0; target=2; dist=[0, 1, -1]; queue=deque([1]); u=0; v=1

L8 shortest_hops: u = queue.popleft()
adj=[[1], [], []]; start=0; target=2; dist=[0, 1, -1]; queue=deque([]); u=1; v=1

Why the solution is correct

Inductively, all vertices at distance at most d are discovered before processing the next layer. A newly discovered neighbor has a length-(d+1) route, and a shorter route would already have discovered it. Therefore every assigned distance is minimal, including the returned target distance.

Time and space

O(V+E) time and O(V) auxiliary distance/queue storage.

Common mistakes

A DFS visitation distance is not generally shortest. This first-discovery proof fails when edges have unequal weights.

Reasoning card

Transfer exercise

Count shortest paths by accumulating counts when another edge reaches a vertex at its already-known optimal distance.