When a problem asks for a shortest path, three algorithms compete. The cue that decides between them is the edge weights.
The decision table
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| When you see… | …use | Complexity | Fails when | |
| Unweighted edges (or all weight 1) | BFS | O(V + E) | edges have varying weights | |
| Non-negative weighted edges | Dijkstra (heap) | O((V + E) log V) | any negative edge | |
| Some negative edges, no neg cycle | Bellman-Ford | O(V·E) | negative cycle (report it) | |
| All-pairs shortest paths, dense | Floyd-Warshall | O(V³) | very large V | |
| Single target + good heuristic | A* | ≤ Dijkstra | no admissible heuristic |
How to choose, step by step
- Are edges unweighted (or uniform)? → BFS. Level order equals distance; the first time you reach a node is via a shortest path. This includes implicit graphs (word ladder, grid steps).
- Weighted, all non-negative? → Dijkstra. The greedy "finalize the closest unvisited node" works because non-negativity guarantees you never improve a finalized distance later.
- Any negative edge? → Dijkstra breaks (it may finalize a node before a cheaper negative-edge path is discovered). Use Bellman-Ford, which relaxes all edges
V−1times and can also detect negative cycles (aV-th relaxation that still improves something). - Need every pair's distance and
Vis small? → Floyd-Warshall, anO(V³)triple loop. - Single source-to-target with domain knowledge (e.g. straight-line distance on a map)? → A*, which is Dijkstra guided by an admissible heuristic and explores far fewer nodes.
The two classic traps
- 0-1 weights (edges weigh 0 or 1) → don't reach for full Dijkstra; 0-1 BFS with a deque is O(V + E).
- "Cheapest within K stops" → not plain Dijkstra; it's a bounded relaxation, naturally Bellman-Ford-style or BFS with a hop counter, because the state includes stops-used.