Shortest Path — Algorhythm<br>Shortest Path

01 / The shared mechanism<br>Find the shortest route from a source to every other node. The mechanism splits by what the edges carry — uniform costs collapse to BFS, non-negative weights need a priority queue (Dijkstra), negatives demand relaxation rounds (Bellman-Ford), and full transit tables fall to Floyd-Warshall.

02 / The one-sentence essence<br>When every edge costs the same, the first time you reach a node is the shortest way to reach it — so BFS, which visits nodes in increasing order of step-count, doubles as a shortest-path algorithm.

animationcomplexity

Problemshortest path from source on an unweighted graphGraphmeshSourceA?<br>A∞B∞C∞D∞E∞F∞Graph has 6 nodes. Mark every distance as ∞ and seed the queue with the source.

step<br>0 / 24

queue

visited<br>0 / 6

0.5×1×2×<br>0 / 24

sourcegraph<br>diamondmeshchaindisconnectedwith-cycle

03 / The pattern signature<br># BFS from source — every edge has weight 1dist[v] ← ∞ for all vdist[s] ← 0queue ← [s]while queue not empty:u ← queue.pop_front()for v in neighbors(u):if dist[v] = ∞:dist[v] ← dist[u] + 1; queue.push(v)# first visit = shortest distance, because the queue empties layer by layer

04 / When to recognize this pattern<br>"unweighted graph"<br>Edges have no weight, or all weights are equal. Cells in a grid moving one step at a time count as well — the grid is just an implicit graph. If weights differ, BFS no longer gives shortest paths.

"minimum number of steps"<br>The objective counts hops, not cost. "Fewest moves", "minimum operations", "shortest sequence".

"shortest path in a maze"<br>Grid-world phrasing. The 4-neighbor (or 8-neighbor) adjacency makes every cell move one step.

"multi-source"<br>Seed the queue with all sources at distance 0 and BFS once — far cheaper than running BFS from each source independently.

05 / Common pitfalls<br>Using DFS "because it's simpler".<br>DFS visits in some order, not in distance order — the first time it reaches a node may be via a long path. For unweighted shortest paths you must use BFS.

Marking visited on dequeue instead of enqueue.<br>If you only mark visited[v] = true when you pop v from the queue, the same node can sit in the queue multiple times — quadratic blow-up on dense graphs. Mark at the moment you enqueue.

Forgetting that BFS only works for non-negative, uniform costs.<br>The moment edges carry different weights, BFS gives wrong answers. You need Dijkstra (or 0-1 BFS with a deque if weights are only 0 or 1).

06 / Go practice — on LeetCode<br>Four problems, ordered by difficulty. No solutions here, by design.<br>01Shortest Path in Binary Matrix— LC 1091medium→02Rotting Oranges— LC 994medium→0301 Matrix— LC 542medium→04Word Ladder— LC 127hard→

— / When to use which<br>unweighted BFS<br>Use when every edge has the same cost — 1 step = 1 edge.<br>grid · maze · O(V + E)

Dijkstra<br>Use when edge weights are non-negative.<br>priority queue · O((V + E) log V)

Bellman-Ford<br>Use when weights can go negative, or you need cycle detection.<br>V−1 relax rounds · O(V · E)

Floyd-Warshall<br>Use when you need all-pairs distances, not just single-source.<br>DP via intermediates · O(V³)