| Year | Algorithm/Contribution | Contributor(s) | Description | Time Complexity | Relative Improvement |
|---|
| 1951 | Matrix-based shortest paths | A. Shimbel | Introduced a method for unit-length all-pairs shortest paths using matrix powers. | O(n^4) | Baseline for early APSP methods. |
| 1955 | Min-sum algebra for shortest paths | A. Shimbel | Developed min-sum matrix multiplication as precursor to Bellman-Ford. | O(n^4) for APSP | Minor refinement over previous matrix method. |
| 1955 | Shortest path as linear programming | A. Orden | Recognized shortest path as a special case of transshipment problem. | Solvable via LP (polynomial time) | Introduced optimization perspective, no specific speedup quantified. |
| 1956 | Ford's algorithm | L.R. Ford | General relaxation method handling negative weights. | O(VE) worst-case, exponential possible | Flexible for negative weights, but potentially slow. |
| 1957 | Early priority-based method | G.B. Dantzig | Method using smallest d(u) + l(u,v) for nonnegative weights. | O(n^2 log n) | Early improvement for nonnegative weights over relaxation methods. |
| 1957 | Improved all-pairs method | Leyzorek et al. | Speedup of Shimbel's method; early Dijkstra-like description. | O(n^3 log n) for APSP | Factor of n/log n faster than O(n^4) for APSP. |
| 1958 | Bellman-Ford algorithm | R. Bellman | Functional equation approach handling negative weights. | O(V^3) dense or O(VE) | Standardized relaxation, up to n times faster than Ford in practice. |
| 1959 | Dijkstra's algorithm | E.W. Dijkstra | Priority queue-based for single-source with nonnegative weights. | O(V^2) | Up to E/V faster than Bellman-Ford for dense graphs. |
| 1959 | Moore's algorithm | E.F. Moore | Refinement of Bellman's for parallel suitability. | O(VE) | Similar to Bellman-Ford, improved for certain implementations. |
| 1962 | Floyd-Warshall algorithm | R.W. Floyd, S. Warshall | Dynamic programming for all-pairs, handles negative without cycles. | O(V^3) | Matches Bellman dense case, simpler for APSP. |
| 1968 | A* search algorithm | P.E. Hart, N.J. Nilsson, B. Raphael | Heuristic search for pathfinding in AI. | Varies with heuristic | Often faster in practice than Dijkstra with good heuristics. |
| 1977 | Johnson's algorithm | D.B. Johnson | APSP for sparse graphs using reweighting and Dijkstra. | O(V^2 log V + VE) | Improves over Floyd-Warshall for sparse graphs by factor ~V. |
| 1984 | Dijkstra with Fibonacci heaps | M.L. Fredman, R.E. Tarjan | Advanced priority queue for better asymptotic. | O(E + V log V) | Θ(&log V) faster than binary heap O(E log V) for sparse graphs. |
| 1999 | Thorup's algorithm | M. Thorup | Linear time for undirected integer weights. | O(E) | Linear time, breaking polylog factors for specific cases. |
| 2022 | Near-linear algorithm for negative weights | A. Bernstein, D. Nanongkai, C. Wulff-Nilsen | Combinatorial near-linear for SSSP with negative weights. | Near O(E) | Vast improvement over Bellman-Ford's O(VE), near-linear time. |
| 2023 | Optimized negative weight algorithm | K. Bringmann, A. Cassis, N. Fischer | Reduced log factors in negative weight SSSP. | Improved near-linear | Reduces overhead by polylog factors over 2022 method. |
| 2025 | Breaking the Sorting Barrier | Ran Duan and team (Tsinghua University) | Deterministic SSSP for directed graphs with non-negative weights, breaking long-standing barrier. | O(m log2/3 n) | Θ(&log1/3 n) faster than O(m log n) implementations; better for sparse graphs over O(m + n log n). |
