The question: route planning, network analysis and logistics all need shortest paths, and three classic algorithms solve the problem in very different ways. When should you use each one?
What I built: clean implementations of all three, checked against a trusted library and timed as graphs grow.
Correct first
All 100 comparisons with NetworkX match: 30 random graphs for all three algorithms, plus 10 graphs with negative edge weights for Bellman-Ford.
How they scale
Random directed graphs with an average of 4 edges per node, best of 3 runs.
| Nodes | Dijkstra | Bellman-Ford | Floyd-Warshall (all pairs) |
|---|---|---|---|
| 100 | 0.10 ms | 0.24 ms | 48 ms |
| 400 | 0.50 ms | 1.3 ms | 2.74 s |
| 3,200 | 5.6 ms | 18 ms | not run |
| 6,400 | 15 ms | not run | not run |
When to use each
- Dijkstra (binary heap) is the default for non-negative weights: 6,400 nodes in 15 ms in pure Python.
- Bellman-Ford is about 3 times slower here, but it handles negative weights and detects negative cycles.
- Floyd-Warshall grows as V³. At 400 nodes it is 13 times slower than running Dijkstra from every node, so keep it for small or dense graphs.
My first version used adjacency matrices and couldn't load a real road network (264,346 nodes would need about 500 GB as a dense matrix). This version uses adjacency lists.