next up previous contents index CD CD Algorithms
Next: Transitive Closure and Reduction Up: Graph Problems: Polynomial-Time Previous: Minimum Spanning Tree

Shortest Path



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 tex2html_wrap_inline28709 and tex2html_wrap_inline28711 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 gif for more details.

The straightforward implementation of this algorithm is O(m n). However, with simple data structures it can be reduced to tex2html_wrap_inline28717 or tex2html_wrap_inline28719 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:

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 for noncommercial use.

LEDA (see Section gif) 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 gif.

XTango (see Section gif)   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 gif.

    The Stanford GraphBase (see Section gif) 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 gif).   

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 tex2html_wrap_inline28759 [AMOT88], while tex2html_wrap_inline28761 suffices for graphs with negative edge weights [GT89]

Related Problems: Network flow (see page gif), motion planning (see page gif).    

next up previous contents index CD CD Algorithms
Next: Transitive Closure and Reduction Up: Graph Problems: Polynomial-Time Previous: Minimum Spanning Tree

Mon Jun 2 23:33:50 EDT 1997