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 most obvious applications arise in transportation or communications, such as finding the best route to drive between Chicago and Phoenix or figuring how to direct packets to a destination across a network.
•     Consider the problem of image segmentation, that is, separating two characters in a scanned, bit-mapped image of printed text.   We need to find the separating line between two points that cuts through the fewest number of black pixels. This grid of pixels can be modeled as a graph, with any edge across a black pixel given a high cost. The shortest path from top to bottom defines the best separation between left and right.
•     A major problem in speech recognition is distinguishing between words that sound alike (homophones), such as to, two, and too. We can construct a graph whose vertices correspond to possible words, with an edge between possible neighboring words.   If the weight of each edge measures the likelihood of transition, the shortest path across the graph defines the best interpretation of a sentence. For a more detailed account of such an application, see Section .
• Suppose we want to draw an informative picture of a graph.   The center of the page should coorespond to the ``center'' of the graph, whatever that means. A good definition of the center is the vertex that minimizes the maximum distance to any other vertex in the graph. Finding this center point requires knowing the distance (i.e. shortest path) between all pairs of vertices.

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:

• Is your graph weighted or unweighted? - If your graph is unweighted, a simple breadth-first search   starting from the source vertex will find the shortest path in linear time. It is only when edges have different weights that you need more sophisticated algorithms. Breadth-first search is both simpler and faster than Dijkstra's algorithm.
• Does your graph have negative cost weights? -   Dijkstra's algorithm assumes that all edges have positive cost. If your graph has edges with negative weights, you must use the more general but less efficient Bellman-Ford algorithm.     If your graph has a cycle of negative cost, than the shortest path between any two vertices in the graph is not defined, since we can detour to the negative cost cycle and loop around it an arbitrary number of times, making the total cost as small as desired. Note that adding the same amount of weight to each edge to make it positive and running Dijkstra's algorithm does not find the shortest path in the original graph, since paths that use more edges will be rejected in favor of longer paths using fewer edges.

  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.

• Is your input a set of geometric obstacles instead of a graph? -     If you seek the shortest path between two points in a geometric setting, like an obstacle-filled room, you may either convert your problem into a graph of distances and feed it to Dijkstra's algorithm or use a more efficient geometric algorithm to compute the shortest path directly from the arrangement of obstacles.   For such geometric algorithms, see Section on motion planning.
• Does your graph have cycles in it, or is it a DAG? -   If your graph is a directed acyclic graph (DAG), than the shortest path can be found in linear time. Perform a topological sort to order the vertices such that all edges go from left to right, then do dynamic programming on the left-to-right ordered vertices.   Indeed, most dynamic programming problems can be easily formulated as shortest paths on specific DAGs. The algorithm is discussed in [Man89] if you cannot figure it out from this description. Note that the same algorithm (replacing with )   also suffices for finding the longest path in a DAG. which is useful in many applications like scheduling (see Section ).
• Do you need the shortest path between all pairs of points? -   If you are interested in the shortest path between all pairs of vertices, one solution is to run Dijkstra n times, once with each vertex as the source.    However, the Floyd-Warshall algorithm is a slick dynamic programming algorithm for all-pairs shortest path, which is faster and easier to program than Dijkstra and which works with negative cost edges (but not cycles). It is discussed more thoroughly in Section . Let M denote the distance matrix, where if there is no edge (i,j).

  
  
    
  
  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.

• How do I find the shortest cycle in a graph? -       One application of all-pairs shortest path is to find the shortest cycle in a graph, called its girth. Floyd's algorithm can be used to compute for , which is the length of the shortest way to get from vertex i to i, in other words the shortest cycle through i.

  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 ).