Shortest-path algorithms compared
BFS, Dijkstra, Bellman-Ford, Floyd-Warshall and DAG shortest paths: edge weights, negative edges, single-source or all-pairs — one table to pick the right one.
| Algorithm | Time | Space | Weights | Negative edges | Scope | Difficulty |
|---|---|---|---|---|---|---|
| BFSBreadth-first search | O(V+E) | O(V) | All equal (unweighted) | — | Single source | Intro |
| DijkstraSingle-source shortest paths | O((V+E) log V) | O(V) | Non-negative | ✗ | Single source | Intermediate |
| Bellman-FordShortest paths with negative weights | O(VE) | O(V) | Any | ✓, and detects negative cycles | Single source | Hard |
| Floyd-WarshallAll-pairs shortest paths | O(V³) | O(V²) | Any | ✓ (negative cycle shows on the diagonal) | All pairs | Hard |
| Shortest Path in DAGShortest paths on a DAG | O(V+E) | O(V) | Any | ✓ (acyclic, so no negative cycles) | Single source | Intermediate |
When to pick which
Every step costs the same: grids, social distance, number of state transitions. The fastest of the family; use it whenever you can.
The default for weighted graphs: maps, network latency, weighted state graphs. A single negative edge silently breaks it.
Negative edges, negative-cycle detection (arbitrage, exchange rates), or an 'at most k edges' constraint. V·E is slow; reconsider past tens of thousands of vertices.
Every pair's distance, V up to a few hundred, or a dense graph. Three loops in five lines; hard to get wrong.
The graph is guaranteed acyclic: scheduling, critical paths, DP state graphs. One relaxation pass in topological order, O(V+E), and it finds longest paths too.
Choosing guide
- Unweighted → BFS. Non-negative → Dijkstra. Negative edges → Bellman-Ford. Acyclic → DAG relaxation. All pairs, small V → Floyd-Warshall.
- Weights are only 0 and 1 → 0-1 BFS (a deque: weight 0 to the front, weight 1 to the back), O(V+E) without Dijkstra's log.
- All pairs but large V and sparse edges → run Dijkstra from every vertex; V·(V+E) log V is usually far better than V³.
- Longest path → NP-hard on general graphs; on a DAG negate the weights and run shortest path, or take max along topological order.
- Only reachability, distance irrelevant → DFS or Union-Find is enough; skip shortest paths entirely.