visualization

Graph BFS Shortest Path

First touch wins: BFS hands every node its shortest distance on arrival.

8-node graph · source A · target H · cross edges C–E, E–G, G–H form cyclesstep 1/18

queue (front → back) · node @ distance

A → d=0

Start: A enters the queue at distance 0. BFS will reach every node in order of distance from A.

pseudocode

queue = deque([A]); dist = {A: 0}
parent = {}
while queue:
    node = queue.popleft()
    for nb in adj[node]:
        if nb in dist: continue  # reached earlier = reached shorter
        dist[nb] = dist[node] + 1; parent[nb] = node
        if nb == H: return walk_back(parent, H)
        queue.append(nb)