Dominion Akinrotimi
Back to Projects
PythonAlgorithmsNetworkXBenchmarking

Shortest-Path Algorithms: Dijkstra, Bellman-Ford and Floyd-Warshall

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.

View the code on GitHub

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

Log-log chart of run time against graph size for the three algorithms

Random directed graphs with an average of 4 edges per node, best of 3 runs.

NodesDijkstraBellman-FordFloyd-Warshall (all pairs)
1000.10 ms0.24 ms48 ms
4000.50 ms1.3 ms2.74 s
3,2005.6 ms18 msnot run
6,40015 msnot runnot run

When to use each

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.

Need a tool or data system built?

I design data pipelines, automation and software that hold up in real use.