Content deleted Content added
→Directed graph: I changed one index for better representation |
Update Duan et al. 2025 algorithm description and time complexity |
||
| (35 intermediate revisions by 26 users not shown) | |||
Line 1:
{{short description|Computational problem of graph theory}}
{{More footnotes needed|date=June 2009}}
[[File:Shortest path with direct weights.svg|thumb|upright=1.2|Shortest path (A, C, E, D, F), blue, between vertices A and F in the weighted directed graph]]
In [[graph theory]], the '''shortest path problem''' is the problem of finding a [[path (graph theory)|path]] between two [[vertex (graph theory)|vertices]] (or nodes) in a [[Graph (discrete mathematics)|graph]] such that the sum of the [[Glossary of graph theory terms#weighted graph|weights]] of its constituent edges is minimized.<ref>{{Cite book |url=https://link.springer.com/book/10.1007/978-3-031-02574-7 |title=The Shortest-Path Problem |series=Synthesis Lectures on Theoretical Computer Science |date=2015 |language=en |doi=10.1007/978-3-031-02574-7|isbn=978-3-031-01446-8 }}</ref>
The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length or distance of
==Definition==
The shortest path problem can be defined for [[Graph (discrete mathematics)|graphs]] whether [[Graph (discrete mathematics)#Undirected graph|undirected]], [[Graph (discrete mathematics)#Directed graph|directed]], or [[Mixed graph|mixed]]. The definition for undirected graphs states that every edge can be traversed in either direction. Directed graphs require that consecutive vertices be connected by an appropriate directed edge.<ref>{{cite book |last1=Deo |first1=Narsingh |title=Graph Theory with Applications to Engineering and Computer Science |date=17 August 2016 |publisher=Courier Dover Publications |isbn=978-0-486-80793-5 |url=https://books.google.com/books?id=uk1KDAAAQBAJ |language=en}}</ref>
Two vertices are adjacent when they are both incident to a common edge. A [[Path (graph theory)|path]] in an undirected graph is a [[sequence]] of vertices <math>P = ( v_1, v_2, \ldots, v_n ) \in V \times V \times \cdots \times V</math> such that <math>v_i</math> is adjacent to <math>v_{i+1}</math> for <math>1 \leq i < n</math>. Such a path <math>P</math> is called a path of length <math>n-1</math> from <math>v_1</math> to <math>v_n</math>. (The <math>v_i</math> are variables; their numbering relates to their position in the sequence and need not relate to a canonical labeling.)
Let <math>E = \{e_{i, j}\}</math> where <math>e_{i, j}</math> is the edge incident to both <math>v_i</math> and <math>v_j</math>. Given a [[Function (mathematics)#Real function|real-valued]] weight function <math>f: E \rightarrow \mathbb{R}</math>, and an undirected (simple) graph <math>G</math>, the shortest path from <math>v</math> to <math>v'</math> is the path <math>P = ( v_1, v_2, \ldots, v_n )</math> (where <math>v_1 = v</math> and <math>v_n = v'</math>) that over all possible <math>n</math> minimizes the sum <math>\sum_{i =1}^{n-1} f(e_{i, i+1}).</math> When each edge in the graph has unit weight or <math>f: E \rightarrow \{1\}</math>, this is equivalent to finding the path with fewest edges.
Line 28 ⟶ 21:
==Algorithms==
* [[Dijkstra's algorithm]] solves the single-source shortest path problem with only non-negative edge
* [[Bellman–Ford algorithm]] solves the single-source problem if edge weights may be negative.
* [[A* search algorithm]] solves for single-pair shortest path using heuristics to try to speed up the search.
Line 51 ⟶ 44:
|-
| <math>\mathbb{N}</math> || ''O''(''E'') || {{harvnb|Thorup|1999}} (requires constant-time multiplication)
|-
| <math>\mathbb{R}</math><sub>+</sub> || <math>O(E\sqrt{\log V \log \log V})</math> || {{harvnb|Duan|Mao|Shu|Yin|2023}}
|}
Line 60 ⟶ 55:
|}
===Directed acyclic graphs
An algorithm using [[Topological sorting#Application to shortest path finding|topological sorting]] can solve the single-source shortest path problem in time {{math|Θ(''E'' + ''V'')}} in arbitrarily-weighted
===Directed graphs with nonnegative weights===
Line 78 ⟶ 73:
|-
| <math>\mathbb{R}</math> || [[Dijkstra's algorithm]] with [[binary heap]] || <math> O((E+V)\log{V})</math> || {{harvnb|Johnson|1977}}
|-
| <math>\mathbb{R}</math> || [[Dijkstra's algorithm]] with [[Fibonacci heap]]||<math>O(E+V\log{V})</math> || {{harvnb|Fredman|Tarjan|1984}}, {{harvnb|Fredman|Tarjan|1987}}
|-
| <math>\mathbb{R}</math>
|- style="background: #d0ffd0"
|<math>\mathbb{R}</math>
|[[Dijkstra's algorithm|Dijkstra's]]-[[Bellman–Ford algorithm|Bellman–Ford]] hybrid with a [[Divide-and-conquer algorithm|divide-and-conquer]] frontier reduction
|<math>O(E \log^{2/3}{V})</math>
|{{harvnb|Duan|Mao|Mao|Shu|Yin|2025}}<ref>{{Cite web |last=Brubaker |first=Ben |date=2025-08-06 |title=New Method Is the Fastest Way To Find the Best Routes |url=https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/ |access-date=2025-08-11 |website=Quanta Magazine |language=en}}</ref>
|-
| <math>\mathbb{N}</math> || Dial's algorithm<ref name="dial69">{{cite journal
Line 111:
! Weights !! Algorithm !! Time complexity !! Author
|-
| <math>\mathbb{R}</math> || ||
</ |-
| <math>\mathbb{R}</math> || [[Bellman–Ford algorithm]] ||
|-
| <math>\mathbb{R}</math> || [[Johnson's algorithm|Johnson-Dijkstra]] with [[binary heap]] ||
|-
| <math>\mathbb{R}</math> || [[Johnson's algorithm|Johnson-Dijkstra]] with [[Fibonacci heap]] ||
|-
| <math>\mathbb{
|-
|<math>\mathbb{
|[[Interior-point method]] with Laplacian solver
|<math>O(E^{10/7} \log^{O(1)} V \log^{O(1)} L)</math>
|{{harvnb|Cohen|Mądry|Sankowski|Vladu|2017}}
|-
|<math>\mathbb{Z}</math>
|[[Interior-point method]] with <math>\ell_p</math> flow solver
|<math>E^{4/3 + o(1)} \log^{O(1)} L</math>
|{{harvnb|Axiotis|Mądry|Vladu|2020}}
|-
|<math>\mathbb{Z}</math>
|Robust [[interior-point method]] with sketching
|<math>O((E + V^{3/2}) \log^{O(1)} V \log^{O(1)} L)</math>
|{{harvnb|van den Brand|Lee|Nanongkai|Peng|2020}}
|-
|<math>\mathbb{Z}</math>
| <math>\ell_1</math> [[interior-point method]] with dynamic min-ratio cycle data structure
|<math>O(E^{1+o(1)} \log L)</math>
|{{harvnb|Chen|Kyng|Liu|Peng|2022}}
|-
|<math>\mathbb{Z}</math>
|Based on low-diameter decomposition
|<math>O(E \log^8 V \log L)</math>
|{{harvnb|Bernstein|Nanongkai|Wulff-Nilsen|2022}}
|-
|<math>\mathbb{R}</math>
|Hop-limited shortest paths
|<math>O(E V^{8/9} \log^{O(1)} V)</math>
|{{harvnb|Fineman|2024}}
|}
{{incomplete list|date=December 2012}}
Line 133 ⟶ 159:
! Weights !! Algorithm !! Time complexity !! Author
|-
| <math>\mathbb{Z}</math> ||
|}
Line 142 ⟶ 168:
| <math>\mathbb{R}_{\geq 0}</math> || || <math> O( V )</math> || {{harvnb|Henzinger|Klein|Rao|Subramanian|1997}}
|}
== Applications ==
'''Network flows'''<ref>{{Cite book |last=Cormen |first=Thomas H. |title=Introduction to Algorithms |date=July 31, 2009 |publisher=MIT Press |isbn=9780262533058 |edition=3rd}}</ref> are a fundamental concept in graph theory and operations research, often used to model problems involving the transportation of goods, liquids, or information through a network. A network flow problem typically involves a directed graph where each edge represents a pipe, wire, or road, and each edge has a capacity, which is the maximum amount that can flow through it. The goal is to find a feasible flow that maximizes the flow from a source node to a sink node.
'''Shortest Path Problems''' can be used to solve certain network flow problems, particularly when dealing with single-source, single-sink networks. In these scenarios, we can transform the network flow problem into a series of shortest path problems.
=== Transformation Steps ===
<ref>{{Cite book |last1=Kleinberg |first1=Jon |last2=Tardos |first2=Éva |title=Algorithm Design |publisher=Addison-Wesley |year=2005 |isbn=978-0321295354 |edition=1st |url=http://www.nytimes.com/2009/08/06/technology/06stats.html?_r=2&scp=1&sq=statistics&st=nyt}}</ref>
# '''Create a Residual Graph:'''
#* For each edge (u, v) in the original graph, create two edges in the residual graph:
#** (u, v) with capacity c(u, v)
#** (v, u) with capacity 0
#* The residual graph represents the remaining capacity available in the network.
# '''Find the Shortest Path:'''
#* Use a shortest path algorithm (e.g., Dijkstra's algorithm, Bellman-Ford algorithm) to find the shortest path from the source node to the sink node in the residual graph.
# '''Augment the Flow:'''
#* Find the minimum capacity along the shortest path.
#* Increase the flow on the edges of the shortest path by this minimum capacity.
#* Decrease the capacity of the edges in the forward direction and increase the capacity of the edges in the backward direction.
# '''Update the Residual Graph:'''
#* Update the residual graph based on the augmented flow.
# '''Repeat:'''
#* Repeat steps 2-4 until no more paths can be found from the source to the sink.
==All-pairs shortest paths==
Line 183 ⟶ 232:
If one represents a nondeterministic [[abstract machine]] as a graph where vertices describe states and edges describe possible transitions, shortest path algorithms can be used to find an optimal sequence of choices to reach a certain goal state, or to establish lower bounds on the time needed to reach a given state. For example, if vertices represent the states of a puzzle like a [[Rubik's Cube]] and each directed edge corresponds to a single move or turn, shortest path algorithms can be used to find a solution that uses the minimum possible number of moves.
In a [[Computer network|networking]] or [[Telecommunications network|telecommunications]] mindset, this shortest path problem is sometimes called the min-delay path problem and usually tied with a [[widest path problem]]. For example, the algorithm may seek the shortest (min-delay) widest path, or widest shortest (min-delay) path.<ref>{{Cite book |chapter=K-Shortest Paths Q-Routing: A New QoS Routing Algorithm in Telecommunication Networks |first=S. |last=Hoceini |author2=A. Mellouk |author3=Y. Amirat |date=2005 |chapter-url=https://doi.org/10.1007/978-3-540-31957-3_21 |title=Networking - ICN 2005, Lecture Notes in Computer Science, Vol. 3421 |volume=3421 |pages=164–172 |publisher=Springer, Berlin, Heidelberg |doi=10.1007/978-3-540-31957-3_21 |isbn=978-3-540-25338-9 }}{{cbignore}}</ref>
A more lighthearted application is the games of "[[six degrees of separation]]" that try to find the shortest path in graphs like movie stars appearing in the same film.
Line 215 ⟶ 266:
===Partial observability===
The [[Canadian traveller problem]] and the stochastic shortest path problem are generalizations where either the graph
===Strategic shortest paths===
Line 225 ⟶ 276:
* The [[Bellman–Ford algorithm]] can be used to detect a negative cycle in time <math>O(|V||E|)</math>.
* Cherkassky and Goldberg<ref>{{Cite journal |last1=Cherkassky |first1=Boris V. |last2=Goldberg |first2=Andrew V. |date=1999-06-01 |title=Negative-cycle detection algorithms |url=https://doi.org/10.1007/s101070050058 |journal=Mathematical Programming |language=en |volume=85 |issue=2 |pages=277–311 |doi=10.1007/s101070050058 |s2cid=79739 |issn=1436-4646|url-access=subscription }}</ref> survey several other algorithms for negative cycle detection.
==General algebraic framework on semirings: the algebraic path problem==
Line 251 ⟶ 302:
==Shortest path in stochastic time-dependent networks==
In real-life
There is no accepted definition of optimal path under uncertainty (that is, in stochastic road networks). It is a controversial subject, despite considerable progress during the past decade. One common definition is a path with the minimum expected travel time. The main advantage of this approach is that it can make use of efficient shortest path algorithms for deterministic networks. However, the resulting optimal path may not be reliable, because this approach fails to address travel time variability.
==See also==
Line 277 ⟶ 330:
{{refbegin}}
*{{cite journal |last2=Mehlhorn |first2=Kurt |last3=Orlin |first3=James |last4=Tarjan |first4=Robert E. |date=April 1990 |title=Faster algorithms for the shortest path problem |url=https://apps.dtic.mil/sti/pdfs/ADA194031.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://apps.dtic.mil/sti/pdfs/ADA194031.pdf |archive-date=2022-10-09 |url-status=live |journal=Journal of the ACM |publisher=ACM |volume=37 |issue=2 |pages=213–223 |last1=Ahuja |first1=Ravindra K. |author4-link=Robert Tarjan |doi=10.1145/77600.77615|hdl=1721.1/47994 |s2cid=5499589 |hdl-access=free }}
*{{cite conference
| last1 = Axiotis | first1 = Kyriakos
| last2 = Mądry | first2 = Aleksander
| last3 = Vladu | first3 = Adrian
| editor-last = Irani | editor-first = Sandy
| contribution = Circulation control for faster minimum cost flow in unit-capacity graphs
| doi = 10.1109/FOCS46700.2020.00018
| pages = 93–104
| publisher = IEEE
| title = 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16–19, 2020
| year = 2020| arxiv = 2003.04863
}}
* {{cite journal |last=Bellman |first=Richard |year=1958 |title=On a routing problem |journal=Quarterly of Applied Mathematics |volume=16 |pages=87–90 |mr=0102435 |author-link=Richard Bellman |doi=10.1090/qam/102435|doi-access=free }}
*{{Cite
*{{cite conference
| last1 = van den Brand | first1 = Jan
| last2 = Lee | first2 = Yin Tat
| last3 = Nanongkai | first3 = Danupon
| last4 = Peng | first4 = Richard
| last5 = Saranurak | first5 = Thatchaphol
| last6 = Sidford | first6 = Aaron
| last7 = Song | first7 = Zhao
| last8 = Wang | first8 = Di
| editor-last = Irani | editor-first = Sandy
| contribution = Bipartite matching in nearly-linear time on moderately dense graphs
| doi = 10.1109/FOCS46700.2020.00090
| pages = 919–930
| publisher = IEEE
| title = 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16–19, 2020
| year = 2020| arxiv = 2009.01802
}}
*{{cite conference
| last1 = Chen | first1 = Li
| last2 = Kyng | first2 = Rasmus
| last3 = Liu | first3 = Yang P.
| last4 = Peng | first4 = Richard
| last5 = Gutenberg | first5 = Maximilian Probst
| last6 = Sachdeva | first6 = Sushant
| contribution = Maximum flow and minimum-cost flow in almost-linear time
| doi = 10.1109/FOCS54457.2022.00064
| pages = 612–623
| publisher = IEEE
| title = 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 – November 3, 2022
| year = 2022| arxiv = 2203.00671
}}
*{{cite conference
| last1 = Cohen | first1 = Michael B.
| last2 = Mądry | first2 = Aleksander
| last3 = Sankowski | first3 = Piotr
| last4 = Vladu | first4 = Adrian
| editor-last = Klein | editor-first = Philip N.
| contribution = Negative-weight shortest paths and unit capacity minimum cost flow in <math>\tilde O(m^{10/7}\log W)</math> time
| doi = 10.1137/1.9781611974782.48
| pages = 752–771
| publisher = Society for Industrial and Applied Mathematics
| title = Proceedings of the Twenty-Eighth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16–19
| year = 2017}}
*{{Cite conference |last1=Duan|first1=Ran |last2=Mao |first2=Jiayi |last3=Shu |first3=Xinkai |last4=Yin |first4=Longhui |chapter=A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs |date=2023 |title=2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) |pages=484–492 |publisher=IEEE |doi=10.1109/focs57990.2023.00035|arxiv=2307.04139 |isbn=979-8-3503-1894-4 |s2cid=259501045 }}
*{{cite conference
| last1 = Duan
| first1 = Ran
| last2 = Mao
| first2 = Jiayi
| last3 = Mao
| first3 = Xiao
| last4 = Shu
| first4 = Xinkai
| last5 = Yin
| first5 = Longhui
| contribution = Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
| title = Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC)
| year = 2025
| pages = 36–44
| doi = 10.1145/3717823.3718179
| publisher = Association for Computing Machinery
}}
*{{Cite journal |last2=Goldberg |first2=Andrew V. |last3=Radzik |first3=Tomasz |year=1996 |title=Shortest paths algorithms: theory and experimental evaluation |url=http://ftp.cs.stanford.edu/cs/theory/pub/goldberg/sp-alg.ps.Z |journal=Mathematical Programming |series=Ser. A |volume=73 |issue=2 |pages=129–174 |doi=10.1016/0025-5610(95)00021-6 |mr=1392160 |last1=Cherkassky |first1=Boris V. |author2-link=Andrew V. Goldberg }}
* {{Introduction to Algorithms|edition=2|pages=580–642|chapter=Single-Source Shortest Paths and All-Pairs Shortest Paths}}
*{{cite journal |last=Dantzig |first=G. B. |date=January 1960 |title=On the Shortest Route through a Network |journal=Management Science |volume=6 |issue=2 |pages=187–190 |doi=10.1287/mnsc.6.2.187}}
* {{cite journal |year=1959 |title=A note on two problems in connexion with graphs |journal=Numerische Mathematik |volume=1 |pages=269–271 |doi=10.1007/BF01386390|last1=Dijkstra |first1=E. W. |s2cid=123284777 |author-link=Edsger W. Dijkstra }}
*{{cite conference
| last = Fineman | first = Jeremy T.
| editor1-last = Mohar | editor1-first = Bojan
| editor2-last = Shinkar | editor2-first = Igor
| editor3-last = O'Donnell | editor3-first = Ryan
| arxiv = 2311.02520
| contribution = Single-source shortest paths with negative real weights in <math>\tilde O(mn^{8/9})</math> time
| doi = 10.1145/3618260.3649614
| pages = 3–14
| publisher = Association for Computing Machinery
| title = Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24–28, 2024
| year = 2024}}
* {{cite report |last=Ford |first=L. R. |date=1956 |title=Network Flow Theory |place=Santa Monica, CA |publisher=RAND Corporation |id=P-923 |url=http://www.rand.org/pubs/papers/P923.html}}<!--cited in Dijkstra 1959-->
* {{cite conference |last1=Fredman |first1=Michael Lawrence |author-link1=Michael Fredman |first2=Robert E. |last2=Tarjan |author-link2=Robert Tarjan |title=Fibonacci heaps and their uses in improved network optimization algorithms |conference=25th Annual Symposium on Foundations of Computer Science |year=1984 |publisher=[[IEEE]] |pages=338–346 |isbn=0-8186-0591-X |doi=10.1109/SFCS.1984.715934}}
| |||