Algorithms in a Nutshell

All Pairs Shortest Path | 165

Graph

Algorithms

All Pairs Shortest Path

Instead of finding the shortest path from a single source, we often want to find a

shortest path*between any two vertices (vi,vj). The fastest solution to this problem

uses a powerful problem-solving technique calleddynamic programming.

There are two interesting features of dynamic programming:

• It solves small, constrained versions of the problem. When the constraints are
  tight, the function is simple to compute, and then the constraints are system-
  atically relaxed until finally they yield the value of the desired answer.


• Although one seeks an optimum answer to a problem, it is easier to compute
  thevalueof an optimum answer rather than the answer itself. In our case, we
  compute, for each pair of vertices (vi,vj), the length of a shortest path fromvi
  tovj and perform additional computation to recover the actual path.
  The goal is to compute ann-by-nmatrixdistsuch that for all pairs of vertices
  (vi,vj),dist[i][j]contains the length of a shortest path fromvitovj. The
  pseudocode for FLOYD-WARSHALLis shown in Figure 6-18, together with its
  execution on a small example.

Input

A directed, weighted graphG=(V,E). Each edgee=(u,v) has an associated positive

weight in the graph. The quantityn represents the number of vertices inG.

Output

FLOYD-WARSHALLproduces the matrixdist[][]of values representing the

shortest distance from each vertexuto every vertex in the graph (including itself).

Note that ifdist[u][v]is∞, then there is no path fromutov. The actual shortest

path between any two vertices can be computed from a second matrix,pred[][],

also computed by the algorithm.

Assumptions

The edge weights must be positive (i.e., greater than zero).

Solution

A dynamic programming approach will compute, in order, a series of matrices

distkfor 0≤k≤nsuch thatdistk[i][j] will be the length of a shortest path fromvitovj

that may only pass through verticesv 1 ,v 2 ,...,vkin addition toviandvj.†When

k=0, for instance,dist 0 [i][j] is the weight of the edge (vi,vj), or∞if no such edge

exists. To continue this example, whenk=1, we can determine for alliandj

whether the path of two edges (vi,v 1 ) and (v 1 ,vj) is shorter than the direct edge

(vi,vj). If we continue this logic untilk=n, then we can computedistn[i][j], which

represents the shortest distance fromvitovjpassing through verticesv 1 ,v 2 ,...,vn.

* There may be several paths with the same total distance.

† These vertices are not necessarily distinct; that is,imay equalj or 1≤i≤k or 1≤j≤k.

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use