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.

01 / 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

Graph has 6 nodes. Mark every distance as ∞ and seed the queue with the source.

step

0 / 40

queue

—

visited

0 / 6

0 / 40

sourcegraph

02 / 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

03 / 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.

04 / 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.

ii.

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.

iii.

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).

05 / Go practice — on LeetCode

Four problems, ordered by difficulty. No solutions here, by design.

01Shortest Path in Binary Matrix— LC 1091medium→02Rotting Oranges— LC 994medium→0301 Matrix— LC 542medium→04Word Ladder— LC 127hard→

— / 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³)