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.

Pick a sub-pattern above. Each is independently linkable — start where the problem statement points.

↑ choose one

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