Shortest Path

When every edge costs the same, you never reach for Dijkstra. Plain BFS already hands you the shortest path, no priority queue involved. It works because BFS visits nodes in order of distance, so the first time it touches any node, that's the shortest way there. You'll lean on this more than almost any other graph fact.

The guarantee comes from two things working together: the queue is FIFO, and every edge adds exactly 1 to the distance. Every node at distance d gets enqueued before any node at distance d+1, and since first-in means first-out, it also gets processed first. Picture the queue as concentric rings expanding from the start: ring 0 is the start, ring 1 its direct neighbors, ring 2 their neighbors, and outward from there.

Say the start S has neighbors A, B, C, all at distance 1, so all three enter the queue. When we process A, its unvisited neighbors get added, but they land BEHIND B and C. So B and C, both at distance 1, get processed before any distance-2 node ever does. That's the invariant that turns BFS into a shortest-path algorithm: the queue stays sorted by distance on its own, purely because equal-weight edges bump the distance by exactly 1.