Input description: An edge-weighted graph G, with start vertex and end vertex t.
Problem description: Find the shortest path from to t in G.
Discussion: The problem of finding shortest paths in a graph has a surprising variety of applications:
The primary algorithm for finding shortest paths is Dijkstra's algorithm, which efficiently finds the shortest paths from a given vertex x to all n-1 other vertices. Dijkstra's algorithm starts from x. In each iteration, it identifies a new vertex v for which the shortest path from x to v is known. We maintain a set of vertices S to which we currently know the shortest path from v, and this set grows by one vertex in each iteration. In each iteration, we identify the edge (u,v) where and such that
This edge (u,v) gets added to a shortest path tree, whose root is x and which describes all the shortest paths from x. See the discussion in Section for more details.
The straightforward implementation of this algorithm is O(m n). However, with simple data structures it can be reduced to or time. Theoretically faster times can be achieved using significantly more complicated data structures, as described below. If we are just interested in knowing the shortest path from x to y, simply stop as soon as y enters S.
Dijkstra's algorithm is the right choice for single-source shortest path on positively weighted graphs. However, special circumstances dictate different choices:
Why might one ever need to find shortest paths in graphs with negative cost edges? An interesting application comes in currency speculation. Construct a graph where each vertex is a nation and there is an edge weighted from x to y if the exchange rate from currency x to currency y is w(x,y). In arbitrage, we seek a cycle to convert currencies so that we end up with more money than we started with. For example, if the exchange rates are 12 pesos per dollar, 5 pesos per franc, and 2 francs per dollar, by simply moving money around we can convert $1 to $1.20. In fact, there will be a profit opportunity whenever there exists a negative cost cycle in this weighted graph.
for k = 1 to n do
for i = 1 to n do
for j = 1 to n do
Return
The key to understanding Floyd's algorithm is that denotes ``the length of the shortest path from i to j that goes through at most k intermediate vertices.'' Note that space suffices, since we need keep only and around at time k.
This might be exactly what you want. However, the shortest cycle through x is likely to go from x to y back to x, using the same edge twice. A simple cycle is one that visits no edge or vertex twice. To find the shortest simple cycle, the easiest approach is to compute the lengths of the shortest paths from i to all other vertices, and then explicitly check whether there is an acceptable edge from each vertex back to i.
Figure: The girth, or shortest cycle, in a graph
Finding the longest cycle in a graph includes the special case of Hamiltonian cycle (see ), so it is NP-complete.
The all-pairs shortest path matrix can be used to compute several useful invariants of any graph G, that are related to the center of G. The eccentricity of a vertex v in a graph is the shortest-path distance to the farthest vertex from v. From the eccentricity come other graph invariants. The radius of a graph is the smallest eccentricity of any vertex, while the center is the set of vertices whose eccentricity is the radius. The diameter of a graph is the maximum eccentricity of any vertex.
Implementations: The highest performance code (for both Dijkstra and Bellman-Ford) available for finding shortest paths in graphs is SPLIB [CGR93], developed in C language by Cherkassky, Goldberg, and Radzik. They report solving instances with over one million vertices in under two minutes on a Sun Sparc-10 workstation. Their codes are available from http://www.neci.nj.nec.com/homepages/avg.html for noncommercial use.
LEDA (see Section ) provides good implementations in C++ for all of the shortest-path algorithms we have discussed, including Dijkstra, Bellman-Ford, and Floyd's algorithms.
Pascal implementations of Dijkstra, Bellman-Ford, and Floyd's algorithms are given in [SDK83]. See Section .
XTango (see Section ) includes animations of both Dijkstra's and Floyd's shortest-path algorithms.
Combinatorica [Ski90] provides Mathematica implementations of Dijkstra's and Floyd's algorithms for shortest paths, acyclicity testing, and girth computation for directed/undirected and weighted/unweighted graphs. See Section .
The Stanford GraphBase (see Section ) contains an implementation of Dijkstra's algorithm, used for computing word ladders in a graph defined by five-letter words, as well as an implementation of a program to bound the girth of graphs. Algorithm 562 [Pap80] of the Collected Algorithms of the ACM is a Fortran program to find shortest paths in graphs (see Section ).
Notes: Good expositions on Dijkstra's algorithm [Dij59] and Floyd's all-pairs-shortest-path algorithm [Flo62] include [Baa88, CLR90, Man89]. Good expositions of the Bellman-Ford algorithm [Bel58, FF62] are slightly rarer, but include [CLR90, Eve79a, Law76]. Expositions on finding the shortest path in a DAG include [Law76].
A survey on shortest-path algorithms with 222 references appears in [DP84]. Included are citations to algorithms for related path problems, like finding the kth-shortest path and shortest paths when edge costs vary with time. Expositions on finding the kth-shortest path include [Law76].
The theoretically fastest algorithms known for single-source shortest path for positive edge weight graphs are variations of Dijkstra's algorithm with Fibonacci heaps [FT87]. Experimental studies of shortest-path algorithms include [DF79, DGKK79]. However, these experiments were done before Fibonacci heaps were developed. See [CGR93] for a more recent study.
Theoretically faster algorithms exist when the weights of the edges are small; i.e. their absolute values are each bounded by W. For positive edge weights, the single-source-shortest-path can be found in [AMOT88], while suffices for graphs with negative edge weights [GT89]
Related Problems: Network flow (see page ), motion planning (see page ).