Shortest Path

01 / The shared mechanism

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

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.
Problemshortest path from source on an unweighted graphGraphmeshSourceA
A∞B∞C∞D∞E∞F∞
Graph has 6 nodes. Mark every distance as ∞ and seed the queue with the source.
step
0 / 24
queue
—
visited
0 / 6
0 / 24

03 / The pattern signature

# 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

"unweighted graph"
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"
The objective counts hops, not cost. "Fewest moves", "minimum operations", "shortest sequence".
"shortest path in a maze"
Grid-world phrasing. The 4-neighbor (or 8-neighbor) adjacency makes every cell move one step.
"multi-source"
Seed the queue with all sources at distance 0 and BFS once — far cheaper than running BFS from each source independently.

05 / Common pitfalls

Using DFS "because it's simpler".
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.
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.
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

medium20

01Number of Islands— LC 200→02Perfect Squares— LC 279→03Walls and Gates— LC 286→04Coin Change— LC 322→05Minimum Genetic Mutation— LC 433→06The Maze— LC 490→07The Maze II— LC 505→0801 Matrix— LC 542→09Open the Lock— LC 752→10Snakes and Ladders— LC 909→11Rotting Oranges— LC 994→12Shortest Path in Binary Matrix— LC 1091→13Shortest Path with Alternating Colors— LC 1129→14As Far from Land as Possible— LC 1162→15Jump Game III— LC 1306→16Get Watched Videos by Your Friends— LC 1311→17Shortest Path to Get Food— LC 1730→18Nearest Exit from Entrance in Maze— LC 1926→19K Radius Subarray Averages— LC 2090→20Count Unreachable Pairs of Nodes in an Undirected Graph— LC 2316→

hard7

01Word Ladder II— LC 126→02Word Ladder— LC 127→03Sliding Puzzle— LC 773→04Bus Routes— LC 815→05Shortest Path Visiting All Nodes— LC 847→06K-Similar Strings— LC 854→07Shortest Path in a Grid with Obstacles Elimination— LC 1293→

— / When to use which

unweighted BFS
Use when every edge has the same cost — 1 step = 1 edge.
grid · maze · O(V + E)
Dijkstra
Use when edge weights are non-negative.
priority queue · O((V + E) log V)
Bellman-Ford
Use when weights can go negative, or you need cycle detection.
V−1 relax rounds · O(V · E)
Floyd-Warshall
Use when you need all-pairs distances, not just single-source.
DP via intermediates · O(V³)