Shortest path problem: Difference between revisions

Revision as of 06:42, 27 August 2024

Latest revision as of 21:10, 11 August 2025

(23 intermediate revisions by 16 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 theeach segment.<ref>{{Cite book |last=Guenin |first=Bertrand |title=Gentle Introduction to Optimization |date=2014 |publisher=Cambridge University Press |others=Jochen Koenemann, Levent Tunçel |isbn=978-1-107-05344-1 |edition=1st |___location=West Nyack |pages=27}}</ref>

==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]]. HereThe it is defineddefinition for undirected graphs; forstates directedthat graphsevery theedge definitioncan ofbe pathtraversed in either direction. Directed graphs requiresrequire 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.)

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 here relates to their position in the sequence and needs not to relate to any canonical labeling of the vertices.)

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 26 ⟶ 21:

==Algorithms==

Several well -known algorithms exist for solving this problem and its variants.

* [[Dijkstra's algorithm]] solves the single-source shortest path problem with only non-negative edge weightweights.

* [[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 49 ⟶ 44:

|-

| <math>\mathbb{N}</math> || ''O''(''E'') || {{harvnb|Thorup|1999}} (requires constant-time multiplication)

|-

| <math>\mathbb{R}</math>₊ || <math>O(E\sqrt{\log V \log \log V})</math> || {{harvnb|Duan|Mao|Shu|Yin|2023}}

|}

Line 58 ⟶ 55:

|}

===Directed acyclic graphs (DAGs)===

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 DAGsdirected acyclic graphs.<ref>{{harvnb|Cormen|Leiserson|Rivest|Stein|2001|p=655}}</ref>

===Directed graphs with nonnegative weights===

Line 76 ⟶ 73:

|-

| <math>\mathbb{R}</math> || [[Dijkstra's algorithm]] with [[binary heap]] || <math> O((E+V)\log{V})</math> || {{harvnb|Johnson|1977}}

|-

|- style="background: #d0ffd0"

| <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> || Quantum [[Dijkstra algorithm]] with adjacency list ||<math>O(\sqrt{VE}\log^2{V})</math> || Dürr et al. 2006<ref>{{Cite journal |last1=Dürr |first1=Christoph |last2=Heiligman |first2=Mark |last3=Høyer |first3=Peter |last4=Mhalla |first4=Mehdi |date=January 2006 |title=Quantum query complexity of some graph problems |journal=SIAM Journal on Computing |volume=35 |issue=6 |pages=1310–1328 |doi=10.1137/050644719 |arxiv=quant-ph/0401091 |s2cid=14253494 |issn=0097-5397}}</ref>

|- 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 123 ⟶ 125:

|[[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|Ref=https://doi.org/10.1137/1.9781611974782.48}}

|-

|<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|Ref=https://doi.org/10.1109/FOCS46700.2020.00018}}

|-

|<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, Saranurak, Sidford, Song, Wang|2020|Ref=https://doi.org/10.1109/FOCS46700.2020.00090}}

|-

|<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|Probst|Sachdeva|2022|Ref=https://doi.org/10.1109/FOCS54457.2022.00064}}

|-

|<math>\mathbb{Z}</math>

Line 148 ⟶ 150:

|Hop-limited shortest paths

|<math>O(E V^{8/9} \log^{O(1)} V)</math>

|{{harvnb|Fineman|2023|4=|Ref=https://arxiv.org/abs/2311.025202024}}

|}

{{incomplete list|date=December 2012}}

Line 166 ⟶ 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 207 ⟶ 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 249 ⟶ 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 279 ⟶ 306:

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.

To tackle this issue, some researchers use travel duration distribution instead of its expected value. So, they find the probability distribution of total travel duration using different optimization methods such as [[dynamic programming]] and [[Dijkstra's algorithm]] .<ref>{{cite journal |last1=Olya |first1=Mohammad Hessam |title=Finding shortest path in a combined exponential – gamma probability distribution arc length |journal=International Journal of Operational Research |date=2014 |volume=21 |issue=1|pages=25–37 |doi=10.1504/IJOR.2014.064020 }}</ref> These methods use [[stochastic optimization]], specifically stochastic dynamic programming to find the shortest path in networks with probabilistic arc length.<ref>{{cite journal |last1=Olya |first1=Mohammad Hessam |title=Applying Dijkstra's algorithm for general shortest path problem with normal probability distribution arc length |journal=International Journal of Operational Research |date=2014 |volume=21 |issue=2|pages=143–154 |doi=10.1504/IJOR.2014.064541 }}</ref> The terms ''travel time reliability'' and and ''travel time variability'' are used as opposites in the transportation research literature: the higher the variability, the lower the reliability of predictions.

To account for variability, researchers have suggested two alternative definitions for an optimal path under uncertainty. The ''most reliable path'' is one that maximizes the probability of arriving on time given a travel time budget. An ''α-reliable path'' is one that minimizes the travel time budget required to arrive on time with a given probability.

Line 303 ⟶ 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 bookconference |last1=Bernstein |first1=Aaron |last2=Nanongkai |first2=Danupon |last3=Wulff-Nilsen |first3=Christian |chapter=Negative-Weight Single-Source Shortest Paths in Near-linear Time |date=2022 |title=2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) |pages=600–611 |publisher=IEEE |doi=10.1109/focs54457.2022.00063|arxiv=2203.03456 |isbn=978-1-6654-5519-0 |s2cid=247958461 }}

*{{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}}