# Shortest path problem

The shortest path problem is the problem of finding a path between two vertices in a weighted graph whose sum of edge weights is as small as possible. It is one of the most classic problems in algorithms, studied in variants that fix a single source, a single pair, or all pairs of vertices, and it underlies routing, network optimization, and pathfinding systems.<sup>[1](https://arxiv.org/abs/2609.15247)</sup><sup> • </sup><sup>[2](https://networkx.org/documentation/latest/reference/algorithms/shortest_paths/dijkstra.html)</sup>

| Key fact | Detail |
|---|---|
| Standard variants | Single-source (one vertex to all others), single-pair, and all-pairs; BFS, Dijkstra, and Bellman–Ford serve the first two, Floyd–Warshall and Johnson the last<sup>[3](https://networkx.org/documentation/stable/reference/algorithms/shortest_paths.html?trk=article-ssr-frontend-pulse_little-text-block)</sup> |
| Dijkstra's algorithm | Requires non-negative edge weights; runs in \( O(|V|^{2}) \) with an array, \( O((|V| + |E|) \log |V|) \) with a binary heap, and \( O(|V| \log |V| + |E|) \) with a Fibonacci heap<sup>[2](https://networkx.org/documentation/latest/reference/algorithms/shortest_paths/dijkstra.html)</sup> |
| Bellman–Ford | Handles negative edge weights, runs in \( O(|V| \cdot |E|) \), and detects negative-weight cycles reachable from the source<sup>[3](https://networkx.org/documentation/stable/reference/algorithms/shortest_paths.html?trk=article-ssr-frontend-pulse_little-text-block)</sup><sup> • </sup><sup>[4](https://twiki.di.uniroma1.it/pub/Algoreti/ProgrammaDelCorso/1_1_SingleSourceShortestPaths.pdf)</sup>  |
| Cycles | A shortest path never contains a positive-weight cycle; zero-weight cycles can be removed without changing the weight, so shortest paths may be assumed cycle-free<sup>[4](https://twiki.di.uniroma1.it/pub/Algoreti/ProgrammaDelCorso/1_1_SingleSourceShortestPaths.pdf)</sup> |
| Negative cycles | If a negative-weight cycle is reachable from the source, the shortest-path weight is undefined because looping the cycle lowers the cost without bound<sup>[5](https://mitocw.ups.edu.ec/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-17-bellman-ford/)</sup> |
| 2025 breakthrough | A deterministic \( O(m \log^{2/3} n) \) algorithm for directed single-source shortest paths with non-negative weights, the first to break Dijkstra's \( O(m + n \log n) \) bound on sparse graphs<sup>[6](https://arxiv.org/abs/2504.17033)</sup> |
| Practical routing | Contraction Hierarchies answer queries in milliseconds on road networks with millions of nodes, at the cost of \( O(n^{2}) \) preprocessing space and time<sup>[7](https://arxiv.org/abs/1304.2576)</sup> |

## Problem definition and cycles

Given a graph \( G = (V, E) \) with a weight \( w(u, v) \) on each edge, the weight of a path is the sum of its edge weights, and the shortest-path problem asks for a path of minimum weight between specified vertices. The query type matters: a single-source computation finds paths from one vertex to all reachable vertices, a single-pair query finds one path between two vertices, and all-pairs computations find paths between every pair. A distance query returns only the minimum total weight, while a shortest path query returns the route itself.<sup>[3](https://networkx.org/documentation/stable/reference/algorithms/shortest_paths.html?trk=article-ssr-frontend-pulse_little-text-block)</sup><sup> • </sup><sup>[7](https://arxiv.org/abs/1304.2576)</sup>

**Cycles in shortest paths.** A shortest path cannot contain a negative-weight cycle, and it cannot contain a positive-weight cycle either, because deleting the cycle from the path keeps the same endpoints and lowers the weight. Zero-weight cycles are harmless: removing one from a shortest path leaves another path of the same weight, so whenever a shortest path exists, a cycle-free (simple) shortest path exists as well.<sup>[4](https://twiki.di.uniroma1.it/pub/Algoreti/ProgrammaDelCorso/1_1_SingleSourceShortestPaths.pdf)</sup> Negative-weight cycles are the genuinely destructive case. If such a cycle is reachable from the source, the minimal weight is achieved by walking to the cycle and circling it forever, so the shortest-path weight is meaningless; a correct algorithm must detect and report the cycle rather than return a number.<sup>[8](https://www.cs.mun.ca/~kol/courses/6901-f16/lec8.pdf)</sup><sup> • </sup><sup>[5](https://mitocw.ups.edu.ec/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-17-bellman-ford/)</sup>

## Dijkstra's algorithm

[Dijkstra's algorithm](https://www.edgepedia.org/dijkstras-algorithm), published by [Edsger W. Dijkstra](https://www.edgepedia.org/edsger-w-dijkstra) in a three-page 1959 note in *Numerische Mathematik* (pages 269–271), solves the single-source problem when all edge weights are non-negative.<sup>[9](https://doi.org/10.1007/BF01386390)</sup> It is a greedy, iterative method: it maintains a tentative distance for each vertex, repeatedly selects the unvisited vertex with the smallest tentative distance, marks that distance final, and relaxes the vertex's outgoing edges, updating a neighbor's tentative distance whenever going through the selected vertex would be shorter.<sup>[2](https://networkx.org/documentation/latest/reference/algorithms/shortest_paths/dijkstra.html)</sup>

The non-negativity assumption is what makes the greedy step safe: once a vertex is extracted with the smallest tentative distance, no later path can be shorter. With negative weights this fails. In a standard counterexample, a direct edge of weight 5 from s to t competes with a two-edge path s to v of weight 10 then v to t of weight −7, whose total is 3; Dijkstra's algorithm finalizes t at distance 5 and never corrects it.<sup>[8](https://www.cs.mun.ca/~kol/courses/6901-f16/lec8.pdf)</sup> Adding a constant to every edge weight to make them non-negative does not repair the algorithm, because paths with different numbers of edges are shifted by different amounts.<sup>[10](https://www2.seas.gwu.edu/~simhaweb/cs151/lectures/module9/module9.html)</sup>

## Negative weights and Bellman–Ford

The [Bellman–Ford algorithm](https://www.edgepedia.org/bellman-ford-algorithm) solves the single-source problem with negative edge weights, as long as no negative-weight cycle is reachable from the source. It repeatedly relaxes all edges, and after enough rounds either the distances stabilize or a negative cycle is detected and reported, in which case the computation of the affected shortest paths is aborted.<sup>[4](https://twiki.di.uniroma1.it/pub/Algoreti/ProgrammaDelCorso/1_1_SingleSourceShortestPaths.pdf)</sup><sup> • </sup><sup>[5](https://mitocw.ups.edu.ec/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-17-bellman-ford/)</sup>  Its \( O(|V| \cdot |E|) \) running time stood as the textbook bound for over 60 years; a 2019 algorithm broke it by converting the input graph to non-negative weights using at most \( \min(\sqrt{n}, \sqrt{m/\log n}) \) calls to Dijkstra's algorithm while preserving the shortest-path tree.<sup>[11](https://arxiv.org/abs/1905.01325)</sup>

Two structural special cases avoid the cost of general negative-weight search. In a directed acyclic graph (DAG), a simple algorithm handles negative edge weights, since no cycles of any kind exist.<sup>[12](https://cs61b-2.gitbook.io/cs61b-textbook-spring-2026/23.-reductions-and-decomposition/23.2-shortest-paths-on-dags)</sup> In undirected graphs, the directed reduction techniques break down with negative weights even when no negative cycle exists, and the problem is instead solved by reduction to weighted non-bipartite matching.<sup>[13](https://www.cs.princeton.edu/courses/archive/fall14/cos226/lectures/65Reductions.pdf)</sup>

## All-pairs and reweighting

For all-pairs shortest paths, Floyd–Warshall runs in \( O(|V|^{3}) \) and is suited to dense graphs, while Johnson's algorithm targets sparse graphs with negative weights: it runs Bellman–Ford once to compute a price vector that reweights every edge to be non-negative, then applies Dijkstra's algorithm from each vertex.<sup>[3](https://networkx.org/documentation/stable/reference/algorithms/shortest_paths.html?trk=article-ssr-frontend-pulse_little-text-block)</sup><sup> • </sup><sup>[14](https://arxiv.org/abs/2109.01872)</sup>  When no negative edge is present, running Dijkstra from every vertex works better than Floyd–Warshall on sparse graphs.<sup>[14](https://arxiv.org/abs/2109.01872)</sup>

## Recent theoretical progress

For decades the best bound for non-negative single-source shortest paths in the comparison-addition model was Dijkstra's \( O(m + n \log n) \) with [Fibonacci](https://www.edgepedia.org/fibonacci) heaps. In 2025, Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, and Longhui Yin gave a deterministic \( O(m \log^{2/3} n) \)-time algorithm for directed graphs, the first to break that bound on sparse graphs and to show that Dijkstra's algorithm is not optimal for the problem.<sup>[6](https://arxiv.org/abs/2504.17033)</sup><sup> • </sup><sup>[1](https://arxiv.org/abs/2609.15247)</sup>  A 2026 follow-up by an overlapping group improved the directed bound to \( O(m \sqrt{\log n} + \sqrt{mn \log n \log \log n}) \), which is \( O(m \sqrt{\log n \log \log n}) \) for sparse graphs.<sup>[15](https://arxiv.org/abs/2602.07868)</sup> For undirected graphs, a randomized \( O(m \log^{1/2} n \log\log^{1/2} n) \) algorithm had appeared at FOCS 2023, and further improvements have followed.<sup>[1](https://arxiv.org/abs/2609.15247)</sup>

Negative-weight shortest paths have also advanced rapidly. A 2025 algorithm gives the first deterministic nearly-linear time solution for directed graphs with negative integer weights, running in \( \tilde{O}(m) \cdot \log(nW) \) time and either computing all distances or reporting a negative cycle; it introduces a structural primitive called the path cover.<sup>[16](https://arxiv.org/abs/2511.08551)</sup> A parallel randomized algorithm with near-linear \( \tilde{O}(m) \) work for negative-weight single-source shortest paths in general graphs appeared at SOSA 2025.<sup>[17](https://epubs.siam.org/doi/10.1137/1.9781611978315.17)</sup> These asymptotic wins have not displaced the classical methods in practice: benchmarks report that well-tuned Dijkstra remains 3 to 4 times quicker on real-world graphs because the new algorithms have large constant factors.<sup>[18](https://www.danilchenko.dev/posts/faster-than-dijkstra/)</sup>

## Applications

Shortest path computation is the formal core of route planning: in a road network, nodes represent intersections, edges carry traversal times, and routing a user is a shortest path query.<sup>[19](https://arxiv.org/abs/1910.12526)</sup> Plain Dijkstra is too slow for continental-sized networks, so speed-up techniques dominate practice. Contraction Hierarchies insert shortcut edges in a preprocessing step and answer queries in milliseconds on networks with millions of nodes, though their \( O(n^{2}) \) preprocessing cost is asymptotically worse than Dijkstra's algorithm itself.<sup>[7](https://arxiv.org/abs/1304.2576)</sup> The Arterial Hierarchy index preprocesses a continent-scale network with 23 million nodes in about three hours, producing an index of no more than 32 GB, and answers distance queries in \( \tilde{O}(\log \alpha) \) time, where \( \alpha = d_{max}/d_{min} \) is the ratio of the largest to smallest \( L_{\infty} \) distance between nodes.<sup>[7](https://arxiv.org/abs/1304.2576)</sup> A* search, which accelerates Dijkstra with a distance-estimating heuristic, supports extended scenarios such as live traffic and turn restrictions with less implementation complexity than extending the hierarchical techniques.<sup>[19](https://arxiv.org/abs/1910.12526)</sup>

Beyond navigation, [shortest path algorithms](https://www.edgepedia.org/shortest-path-algorithm) are standard tools in geographic information systems for supply chain optimization, alongside the traveling salesman and vehicle routing problems; the shortest path algorithm searches for the lowest-cost path between a starting point and a destination in a network of locations.<sup>[20](https://www.gis.fhwa.dot.gov/newsletters/Newsletter_February2022.aspx)</sup> A comparative study of Dijkstra and Bellman–Ford for shortest path optimization found Dijkstra better in execution time and more efficient overall, with the caveat that it works only with non-negative edge weights.<sup>[21](https://doi.org/10.1088/1757-899X%2F917%2F1%2F012077)</sup>

## References

1. [A Faster Undirected Single-Source Shortest Path Algorithm (arXiv:2609.15247)](https://arxiv.org/abs/2609.15247)
2. [Dijkstra's Algorithm, NetworkX documentation](https://networkx.org/documentation/latest/reference/algorithms/shortest_paths/dijkstra.html)
3. [Shortest Paths, NetworkX documentation](https://networkx.org/documentation/stable/reference/algorithms/shortest_paths.html?trk=article-ssr-frontend-pulse_little-text-block)
4. [Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Chapter 24: Single-Source Shortest Paths (course excerpt)](https://twiki.di.uniroma1.it/pub/Algoreti/ProgrammaDelCorso/1_1_SingleSourceShortestPaths.pdf)
5. [Lecture 17: Bellman-Ford, MIT 6.006 Introduction to Algorithms, MIT OpenCourseWare](https://mitocw.ups.edu.ec/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-17-bellman-ford/)
6. [Duan, Mao, Mao, Shu, Yin (2025). Breaking the Sorting Barrier for Directed Single-Source Shortest Paths. arXiv:2504.17033](https://arxiv.org/abs/2504.17033)
7. [Zhu et al. (2013). Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice. arXiv:1304.2576](https://arxiv.org/abs/1304.2576)
8. [Kolokolova, A. (2016). CS 6901 Applied Algorithms, Lecture 8: Single-source shortest path with negative weights/cycles](https://www.cs.mun.ca/~kol/courses/6901-f16/lec8.pdf)
9. [Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271](https://doi.org/10.1007/BF01386390)
10. [Module 9: Shortest Paths and Dynamic Programming, Algorithms and Data Structures II, George Washington University](https://www2.seas.gwu.edu/~simhaweb/cs151/lectures/module9/module9.html)
11. [Breaking the Bellman-Ford Shortest-Path Bound (arXiv:1905.01325)](https://arxiv.org/abs/1905.01325)
12. [Shortest Paths on DAGs, CS61B Textbook Spring 2026](https://cs61b-2.gitbook.io/cs61b-textbook-spring-2026/23.-reductions-and-decomposition/23.2-shortest-paths-on-dags)
13. [Reductions, COS 226 Lecture 6.5, Princeton University](https://www.cs.princeton.edu/courses/archive/fall14/cos226/lectures/65Reductions.pdf)
14. [Improving The Floyd-Warshall All Pairs Shortest Paths Algorithm (arXiv:2109.01872)](https://arxiv.org/abs/2109.01872)
15. [Duan, Mao, Shu, Yin (2026). A Faster Directed Single-Source Shortest Path Algorithm. arXiv:2602.07868](https://arxiv.org/abs/2602.07868)
16. [Haeupler, Jiang, Saranurak (2025). Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers. arXiv:2511.08551](https://arxiv.org/abs/2511.08551)
17. [Fischer, Haeupler, Latypov, Roeyskoe, Sulser (2025). A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Path. SOSA 2025](https://epubs.siam.org/doi/10.1137/1.9781611978315.17)
18. [Faster Than Dijkstra: New Shortest-Path Algorithm Explained](https://www.danilchenko.dev/posts/faster-than-dijkstra/)
19. [Strasser, B., Zeitz, T. (2021). A Fast and Tight Heuristic for A* in Road Networks. arXiv:1910.12526](https://arxiv.org/abs/1910.12526)
20. [GIS in Transportation Newsletter, February 2022, Federal Highway Administration](https://www.gis.fhwa.dot.gov/newsletters/Newsletter_February2022.aspx)
21. [Comparative Analysis between Dijkstra and Bellman-Ford Algorithms in Shortest Path Optimization, IOPscience](https://doi.org/10.1088/1757-899X%2F917%2F1%2F012077)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Computational graph problems and algorithms › Shortest-path problems and algorithms*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license