Shortest path problem

6
4
3

to a common edge. A path in an undirected graph is a

sequence of vertices P = (v1 , v2 , . . . , vn ) V V
. . . V such that vi is adjacent to vi+1 for 1 i < n .
Such a path P is called a path of length n 1 from v1 to
vn . (The vi 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 ei,j be the edge incident to both vi and vj . Given a

real-valued weight function f : E R , and an undirected (simple) graph G , the shortest path from v to v
is the path P = (v1 , v2 , . . . , vn ) (where v1 = v and

v
n = v ) that over all possible n minimizes the sum
n1
i=1 f (ei,i+1 ). When each edge in the graph has unit
weight or f : E {1} , this is equivalent to nding the
path with fewest edges.

(6, 4, 5, 1) and (6, 4, 3, 2, 1) are both paths between vertices 6

and 1

The problem is also sometimes called the single-pair

shortest path problem, to distinguish it from the following variations:
The single-source shortest path problem, in
which we have to nd shortest paths from a source
vertex v to all other vertices in the graph.
The single-destination shortest path problem, in
which we have to nd shortest paths from all vertices
in the directed graph to a single destination vertex
v. This can be reduced to the single-source shortest
path problem by reversing the arcs in the directed
graph.

Shortest path (A, C, E, D, F) between vertices A and F in the

weighted directed graph

In graph theory, the shortest path problem is the problem of nding a path between two vertices (or nodes) in
a graph such that the sum of the weights of its constituent
edges is minimized.

The all-pairs shortest path problem, in which we

have to nd shortest paths between every pair of vertices v, v' in the graph.

The problem of nding the shortest path between two

intersections on a road map (the graphs vertices correspond to intersections and the edges correspond to road
segments, each weighted by the length of its road segment) may be modeled by a special case of the shortest
path problem in graphs.

These generalizations have signicantly more ecient algorithms than the simplistic approach of running a singlepair shortest path algorithm on all relevant pairs of vertices.

2 Algorithms
1

Denition

The most important algorithms for solving this problem

The shortest path problem can be dened for graphs are:
whether undirected, directed, or mixed. It is dened here
Dijkstras algorithm solves the single-source shortest
for undirected graphs; for directed graphs the denition
path problem.
of path requires that consecutive vertices be connected by
an appropriate directed edge.
BellmanFord algorithm solves the single-source
problem if edge weights may be negative.

Two vertices are adjacent when they are both incident

1

5 APPLICATIONS
A* search algorithm solves for single pair shortest
path using heuristics to try to speed up the search.

4 All-pairs shortest paths

The all-pairs shortest path problem nds the shortest

FloydWarshall algorithm solves all pairs shortest
paths between every pair of vertices v, v' in the graph.
paths.
The all-pairs shortest paths problem for unweighted di Johnsons algorithm solves all pairs shortest paths, rected graphs was introduced by Shimbel (1953), who
and may be faster than FloydWarshall on sparse observed that it could be solved by a linear number of
matrix multiplications that takes a total time of O(V 4 ).
graphs.
Viterbi algorithm solves the shortest stochastic path
problem with an additional probabilistic weight on 4.1
each node.

Undirected graph

4.2 Directed graph

Additional algorithms and associated evaluations may be

found in Cherkassky, Goldberg & Radzik (1996).

3
3.1

Single-source shortest paths

Undirected graphs

5 Applications
Shortest path algorithms are applied to automatically nd
directions between physical locations, such as driving
directions on web mapping websites like MapQuest or
Google Maps. For this application fast specialized algorithms are available.[1]

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
3.3 Directed acyclic graphs
to nd an optimal sequence of choices to reach a certain
An algorithm using topological sorting can solve the goal state, or to establish lower bounds on the time needed
single-source shortest path problem in linear time, (E to reach a given state. For example, if vertices represent
the states of a puzzle like a Rubiks Cube and each di+ V), in weighted DAGs.
rected edge corresponds to a single move or turn, shortest
path algorithms can be used to nd a solution that uses
3.4 Directed graphs with nonnegative the minimum possible number of moves.

3.2

Unweighted graphs

weights

In a networking or telecommunications mindset, this

shortest path problem is sometimes called the min-delay
The following table is taken from Schrijver (2004). A path problem and usually tied with a widest path problem.
green background indicates an asymptotically best bound For example, the algorithm may seek the shortest (mindelay) widest path, or widest shortest (min-delay) path.
in the table.
This list is incomplete; you can help by
expanding it.

3.5
3.6

Planar directed graphs with nonnegative weights

Other applications, often studied in operations research,

include plant and facility layout, robotics, transportation,
and VLSI design.[2]

5.1 Road networks

Directed graphs with arbitrary weights
A road network can be considered as a graph with posiwithout negative cycles

tive weights. The nodes represent road junctions and each

edge of the graph is associated with a road segment between two junctions. The weight of an edge may correspond to the length of the associated road segment, the
time needed to traverse the segment or the cost of traversing the segment. Using directed edges it is also possiPlanar directed graphs with arbitrary ble to model one-way streets. Such graphs are special in
the sense that some edges are more important than othweights
ers for long distance travel (e.g. highways). This prop-

This list is incomplete; you can help by

expanding it.

3.7

A more lighthearted application is the games of "six degrees of separation" that try to nd the shortest path in
graphs like movie stars appearing in the same lm.

3
erty has been formalized using the notion of highway
dimension.[3] There are a great number of algorithms that
exploit this property and are therefore able to compute
the shortest path a lot quicker than would be possible on
general graphs.
All of these algorithms work in two phases. In the
rst phase, the graph is preprocessed without knowing
the source or target node. The second phase is the
query phase. In this phase, source and target node are
known.The idea is that the road network is static, so the
preprocessing phase can be done once and used for a large
number of queries on the same road network.
The algorithm with the fastest known query time is called
hub labeling and is able to compute shortest path on the
road networks of Europe or the USA in a fraction of a
microsecond.[4] Other techniques that have been used are:
ALT
Arc Flags

nication network, in which each edge is a computer that

possibly belongs to a dierent person. Dierent computers have dierent transmission speeds, so every edge in
the network has a numeric weight equal to the number of
milliseconds it takes to transmit a message. Our goal is
to send a message between two points in the network in
the shortest time possible. If we know the transmissiontime of each computer (-the weight of each edge), then
we can use a standard shortest-paths algorithm. If we do
not know the transmission times, then we have to ask each
computer to tell us its transmission-time. But, the computers may be selsh: a computer might tell us that its
transmission time is very long, so that we will not bother
it with our messages. A possible solution to this problem
is to use a variant of the VCG mechanism, which gives
the computers an incentive to reveal their true weights.

7 Linear programming formulation

Contraction hierarchies
Transit Node Routing
Reach based Pruning
Labeling

Related problems

For shortest path problems in computational geometry,

see Euclidean shortest path.
The travelling salesman problem is the problem of nding the shortest path that goes through every vertex exactly once, and returns to the start. Unlike the shortest
path problem, which can be solved in polynomial time
in graphs without negative cycles, the travelling salesman
problem is NP-complete and, as such, is believed not to
be eciently solvable for large sets of data (see P = NP
problem). The problem of nding the longest path in a
graph is also NP-complete.

There is a natural linear programming formulation for the

shortest path problem, given below. It is very simple compared to most other uses of linear programs in discrete
optimization, however it illustrates connections to other
concepts.
Given a directed graph (V, A) with source node s, target
node t, and cost wij for each edge (i, j) in A, consider the
program with variables xij

minimize
ijA wij
xij subjectto x
0 and for all i,
j xji
j xij

ifi = s;
1,
1, ifi = t;

0,
otherwise.

The intuition behind this is that xij is an indicator variable

for whether edge (i, j) is part of the shortest path: 1 when
it is, and 0 if it is not. We wish to select the set of edges
with minimal weight, subject to the constraint that this
set forms a path from s to t (represented by the equality
The Canadian traveller problem and the stochastic shortconstraint: for all vertices except s and t the number of
est path problem are generalizations where either the
incoming and outcoming edges that are part of the path
graph isn't completely known to the mover, changes over
must be the same (i.e., that it should be a path from s to
time, or where actions (traversals) are probabilistic.
t).
The shortest multiple disconnected path [5] is a represenThis LP has the special property that it is integral; more
tation of the primitive path network within the framework
specically, every basic optimal solution (when one exof Reptation theory.
ists) has all variables equal to 0 or 1, and the set of edges
The widest path problem seeks a path so that the mini- whose variables equal 1 form an s-t dipath. See Ahuja et
mum label of any edge is as large as possible.
al.[6] for one proof, although the origin of this approach
dates back to mid-20th century.

6.1

Strategic shortest-paths

Sometimes, the edges in a graph have personalities: each

edge has its own selsh interest. An example is a commu-

The dual for this linear program is

maximize yt y subject to for all ij, yj yi
wij

10

and feasible duals correspond to the concept of a

consistent heuristic for the A* algorithm for shortest

paths. For any feasible dual y the reduced costs wij

=
wij yj + yi are nonnegative and A* essentially runs
Dijkstras algorithm on these reduced costs.

General algebraic framework on

semirings: the algebraic path
problem

Many problems can be framed as a form of the shortest path for some suitably substituted notions of addition along a path and taking the minimum. The general approach to these is to consider the two operations to
be those of a semiring. Semiring multiplication is done
along the path, and the addition is between paths. This
general framework is known as the algebraic path problem.[7][8][9]
Most of the classic shortest-path algorithms (and new
ones) can be formulated as solving linear systems over
such algebraic structures.[10]
More recently, an even more general framework for solving these (and much less obviously related problems)
has been developed under the banner of valuation algebras.[11]

See also
Pathnding
IEEE 802.1aq
Flow network
Shortest path tree
Euclidean shortest path
Min-plus matrix multiplication
Bidirectional search, an algorithm that nds the
shortest path between two vertices on a directed
graph

10
10.1

References
Notes

[1] Sanders, Peter (March 23, 2009). Fast route planning.

Google Tech Talk.
[2] Chen, Danny Z. (December 1996). Developing algorithms and software for geometric path planning
problems. ACM Computing Surveys 28 (4es): 18.
doi:10.1145/242224.242246.

REFERENCES

[3] Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. Highway Dimension, Shortest Paths,
and Provably Ecient Algorithms. ACM-SIAM Symposium on Discrete Algorithms, pages 782-793, 2010.
[4] Abraham, Ittai; Delling, Daniel; Goldberg, Andrew
V.; Werneck, Renato F. research.microsoft.com/pubs/
142356/HL-TR.pdf A Hub-Based Labeling Algorithm
for Shortest Paths on Road Networks. Symposium on
Experimental Algorithms, pages 230-241, 2011.
[5] Kroger, Martin (2005). Shortest multiple disconnected path for the analysis of entanglements in twoand three-dimensional polymeric systems.
Computer Physics Communications 168 (168): 209232.
doi:10.1016/j.cpc.2005.01.020.
[6] Ravindra K. Ahuja, Thomas L. Magnanti, and James B.
Orlin (1993). Network Flows: Theory, Algorithms and
Applications. Prentice Hall. ISBN 0-13-617549-X.
[7] John Baras; George Theodorakopoulos (4 April 2010).
Path Problems in Networks. Morgan & Claypool Publishers. pp. 9. ISBN 978-1-59829-924-3.
[8] Mehryar Mohri, "Semiring frameworks and algorithms
for shortest-distance problems", Journal of Automata,
Languages and Combinatorics, Volume 7 Issue 3, January
2002, Pages 321 - 350
[9] http://www.iam.unibe.ch/~{}run/talks/
2008-06-05-Bern-Jonczy.pdf
[10] Michel Gondran; Michel Minoux (2008). Graphs, Dioids
and Semirings: New Models and Algorithms. Springer Science & Business Media. chapter 4. ISBN 978-0-38775450-5.
[11] Marc Pouly; Jrg Kohlas (2011). Generic Inference: A
Unifying Theory for Automated Reasoning. John Wiley &
Sons. Chapter 6. Valuation Algebras for Path Problems.
ISBN 978-1-118-01086-0.

10.2 Bibliography
Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James;
Tarjan, Robert E. (April 1990). Faster algorithms
for the shortest path problem. Journal of the ACM
(ACM) 37 (2): 213223.
Bellman, Richard (1958). On a routing problem.
Quarterly of Applied Mathematics 16: 8790. MR
0102435.
Cherkassky, Boris V.; Goldberg, Andrew V.;
Radzik, Tomasz (1996). Shortest paths algorithms: theory and experimental evaluation. Mathematical Programming. Ser. A 73 (2): 129
174. doi:10.1016/0025-5610(95)00021-6. MR
1392160.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest,
Ronald L.; Stein, Cliord (2001) [1990]. SingleSource Shortest Paths and All-Pairs Shortest Paths.

10.3

Missing references
Introduction to Algorithms (2nd ed.). MIT Press and
McGraw-Hill. pp. 580642. ISBN 0-262-03293-7.

Dantzig, G. B. (January 1960). On the Shortest

Route through a Network. Management Science 6
(2): 187190.
Dijkstra, E. W. (1959). A note on two problems in
connexion with graphs (PDF). Numerische Mathematik 1: 269271. doi:10.1007/BF01386390.
Ford, L. R. (1956). Network Flow Theory. Rand
Corporation. P-923.
Fredman, Michael Lawrence; Tarjan, Robert
Fibonacci heaps and their uses
E. (1984).
in improved network optimization algorithms.
25th Annual Symposium on Foundations
of Computer Science. IEEE. pp. 338346.
doi:10.1109/SFCS.1984.715934. ISBN 0-81860591-X.
Fredman, Michael Lawrence; Tarjan, Robert E.
(1987). Fibonacci heaps and their uses in improved
network optimization algorithms. Journal of the
Association for Computing Machinery 34 (3): 596
615. doi:10.1145/28869.28874.
Gabow, H. N. (1983).
Scaling algorithms
for network problems.
Proceedings of the
24th Annual Symposium on Foundations of Computer Science (FOCS 1983).
pp.
248258.
doi:10.1109/SFCS.1983.68.
Gabow, Harold N. (1985). Scaling algorithms for
network problems. Journal of Computer and System Sciences 31 (2): 148168. doi:10.1016/00220000(85)90039-X. MR 828519.
Hagerup, Torben (2000). Montanari, Ugo; Rolim,
Jos D. P.; Welzl, Emo, eds. Improved Shortest
Paths on the Word RAM. Proceedings of the 27th
International Colloquium on Automata, Languages
and Programming. pp. 6172. ISBN 3-540-677151.
Johnson, Donald B. (December 1981). A priority
queue in which initialization and queue operations
take O(log log D) time. Mathematical Systems Theory 15 (1): 295309. doi:10.1007/BF01786986.
MR 683047.
Karlsson, Rolf G.; Poblete, Patricio V. (1983).
An O(m log log D) algorithm for shortest
paths. Discrete Applied Mathematics 6 (1): 91
93.
doi:10.1016/0166-218X(83)90104-X. MR
700028.

5
Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology.
Moore, E. F. (1959). The shortest path through
a maze. Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 25 April 1957). Cambridge: Harvard
University Press. pp. 285292.
Pettie, Seth; Ramachandran, Vijaya (2002).
Computing shortest paths with comparisons and
additions. Proceedings of the thirteenth annual
ACM-SIAM symposium on Discrete algorithms. pp.
267276. ISBN 0-89871-513-X.
Pettie, Seth (26 January 2004). A new approach
to all-pairs shortest paths on real-weighted graphs.
Theoretical Computer Science 312 (1): 4774.
Pollack, M.; Wiebenson, W. (MarchApril 1960).
Solution of the Shortest-Route ProblemA Review. Op. Res. 8 (2): 224230.
Schrijver, Alexander (2004). Combinatorial Optimization Polyhedra and Eciency. Algorithms
and Combinatorics 24. Springer. ISBN 3-54020456-3. Here: vol.A, sect.7.5b, p.103
Shimbel, Alfonso (1953).
Structural parameters of communication networks.
Bulletin
of Mathematical Biophysics 15 (4): 501507.
doi:10.1007/BF02476438.
Thorup, Mikkel (1999). Undirected single-source
shortest paths with positive integer weights in linear
time. Journal of the ACM (JACM) 46 (3): 362394.
Retrieved 28 November 2014.
Thorup, Mikkel (2004). Integer priority queues
with decrease key in constant time and the single source shortest paths problem. Journal of
Computer and System Sciences 69 (3): 330353.
doi:10.1016/j.jcss.2004.04.003.
Whiting, P. D.; Hillier, J. A. (MarchJune 1960).
A Method for Finding the Shortest Route through
a Road Network. Operational Research Quarterly
11 (1/2): 3740.
Williams, Ryan (2014). Faster all-pairs shortest
paths via circuit complexity. Proceedings of the
46th Annual ACM Symposium on Theory of Computing (STOC '14). New York: ACM. pp. 664673.
arXiv:1312.6680. doi:10.1145/2591796.2591811.
MR 3238994.

Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew,

W. C.; Meaker, S. R., Jr.; Petry, R. M.; Seitz, R. N. 10.3 Missing references
(1957). Investigation of Model Techniques First
Dantzig (1958). Missing or empty |title= (help)
Annual Report 6 June 1956 1 July 1957 A

11 FURTHER READING

11

Further reading

Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U.

(1998). Fully dynamic output bounded single
source shortest path problem. Proc. 7th Annu.
ACM-SIAM Symp. Discrete Algorithms. Atlanta,
GA. pp. 212221.
Dreyfus, S. E. (October 1967). An Appraisal of
Some Shortest Path Algorithms (PDF) (Report).
Project Rand. United States Air Force. RM-5433PR. DTIC AD-661265.

12
12.1

Text and image sources, contributors, and licenses

Text

Shortest path problem Source: https://en.wikipedia.org/wiki/Shortest_path_problem?oldid=713149547 Contributors: AxelBoldt, General Wesc, LC~enwiki, The Anome, Shd~enwiki, JeLuF, B4hand, Michael Hardy, Booyabazooka, Ijon, Dcoetzee, Dysprosia, Pigorsch,
Altenmann, Lzur, Sho Uemura, Giftlite, Wolfkeeper, BenFrantzDale, Andris, Lqs, OverlordQ, Andreas Kaufmann, Rich Farmbrough,
Rasmusdf, DcoetzeeBot~enwiki, ESkog, TerraFrost, Brian0918, MisterSheik, Caesura, Oleg Alexandrov, Nuno Tavares, Mindmatrix,
Camw, Oliphaunt, Ruud Koot, BD2412, Qwertyus, Rjwilmsi, Xperimental~enwiki, Mathbot, Mathiastck, Choess, Kri, Cthe, Chobot,
Phelanpt, Chris Capoccia, Gaius Cornelius, Anomie, Nethgirb, Lt-wiki-bot, Cedar101, Treesmill, SmackBot, Mcld, Ohnoitsjamie, DHNbot~enwiki, Tommyjb, Lpgeen, RomanSpa, MadScientistVX, Optakeover, Graph Theory page blanker, Devis, Headbomb, Squire55,
David Eppstein, Kope, Glrx, R'n'B, Edepot, Essess, Dmforcier, Alcidesfonseca, Aaron Rotenberg, Alfredo J. Herrera Lago, Kbrose, SieBot,
Taemyr, Lourakis, Jdaloner, Hariva, Denisarona, Justin W Smith, Metaprimer, Cairomax, Daveagp, Marc van Leeuwen, C. lorenz, Addbot,
Fgnievinski, Jason.surratt, Download, Delaszk, Cipher1024, WikiDreamer Bot, Jarble, Luckas-bot, Yobot, AnomieBOT, Erel Segal, Materialscientist, Citation bot, Xqbot, Alexander Anoprienko, Pmlineditor, Suzhouwuyue, Captain-n00dle, Deanphd, Citation bot 1, RedBot,
Serols, Robert Geisberger, RobinK, Mjs1991, Trappist the monk, MoreNet, Horcrux92, ToneDaBass, John of Reading, WikitanvirBot,
Super48paul, Hari6389, F, Mkroeger, Templatetypedef, ClueBot NG, MiroBrada, Nullzero, BG19bot, Marcelkcs, Happyuk, BattyBot,
Jochen Burghardt, Simonpratt, Amine.marref, HoboMcJoe, Ginsuloft, Robmccoll, Artyom Kalinin, Yacs, Monkbot, JMP EAX, Boky90,
KasparBot, Danieloliveira56, Mikkel2thorup and Anonymous: 118

12.2

Images

File:6n-graf.svg Source: https://upload.wikimedia.org/wikipedia/commons/5/5b/6n-graf.svg License: Public domain Contributors:

Image:6n-graf.png simlar input data Original artist: User:AzaToth
File:Question_book-new.svg Source: https://upload.wikimedia.org/wikipedia/en/9/99/Question_book-new.svg License: Cc-by-sa-3.0
Contributors:
Created from scratch in Adobe Illustrator. Based on Image:Question book.png created by User:Equazcion Original artist:
Tkgd2007
File:Shortest_path_with_direct_weights.svg Source: https://upload.wikimedia.org/wikipedia/commons/3/3b/Shortest_path_with_
direct_weights.svg License: CC BY-SA 3.0 Contributors: Own work Original artist: Artyom Kalinin
File:Text_document_with_red_question_mark.svg Source: https://upload.wikimedia.org/wikipedia/commons/a/a4/Text_document_
with_red_question_mark.svg License: Public domain Contributors: Created by bdesham with Inkscape; based upon Text-x-generic.svg
from the Tango project. Original artist: Benjamin D. Esham (bdesham)
File:Wiki_letter_w_cropped.svg Source: https://upload.wikimedia.org/wikipedia/commons/1/1c/Wiki_letter_w_cropped.svg License:
CC-BY-SA-3.0 Contributors: This le was derived from Wiki letter w.svg: <a href='//commons.wikimedia.org/wiki/File:
Wiki_letter_w.svg' class='image'><img alt='Wiki letter w.svg' src='https://upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Wiki_
letter_w.svg/50px-Wiki_letter_w.svg.png' width='50' height='50' srcset='https://upload.wikimedia.org/wikipedia/commons/thumb/6/6c/
Wiki_letter_w.svg/75px-Wiki_letter_w.svg.png 1.5x, https://upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Wiki_letter_w.svg/
100px-Wiki_letter_w.svg.png 2x' data-le-width='44' data-le-height='44' /></a>
Original artist: Derivative work by Thumperward

12.3

Content license

Creative Commons Attribution-Share Alike 3.0