Algorithms in a Nutshell

All Pairs Shortest Path | 167

Graph

Algorithms

• If it does not, the result of our previous computation,distk–1[i][j], is still our
  best result.


• If it does, such a shortest path can be split into two subpaths: a shortest path
  fromvitovkof lengthdistk–1[i][k] plus a shortest path fromvktovjof length
  distk–1[k][j]. The computed shortest path from vi to vj is then
  distk–1[i][k]+distk–1[k][j].
  Instead of trying to distinguish between these two cases, we compute both values
  and take the smaller. When the smaller value is the second case, FLOYD-
  WARSHALLdetermines that a shorter path exists between vertexiandjthan its
  previous calculation. It may seem surprising that we don’t need to record what
  that path is. Even more surprising is that we only need a single matrixdistrather
  thann+1 matricesdistkbecause we are only concerned with the total distance, not
  the path that involves the fewest number of vertices. The surprisingly brief solu-
  tion is shown in Example 6-7.

Example 6-7. Floyd-Warshall algorithm for computing all pairs shortest path

#include "Graph.h"

void allPairsShortest(Graph const &graph, /* in */

vector< vector<int> > &dist, /* out */

vector< vector<int> > &pred) { /* out */

int n = graph.numVertices( );

// Initialize dist[][] with 0 on diagonals, INFINITY where no edge

// exists, and the weight of edge (u,v) placed in dist[u][v]. pred

// initialized in corresponding way.

for (int u = 0; u < n; u++) {

dist[u].assign(n, numeric_limits<int>::max( ));

pred[u].assign(n, -1);

dist[u][u] = 0;

for (VertexList::const_iterator ci = graph.begin(u);

ci != graph.end(u); ++ci) {

int v = ci->first;

dist[u][v] = ci->second;

pred[u][v] = u;

}

}

for (int k = 0; k < n; k++) {

for (int i = 0; i < n; i++) {

if (dist[i][k] == numeric_limits<int>::max( )) { continue; }

// If an edge is found to reduce distance, update dist[][].

// Compute using longs to avoid overflow of Infinity-distance.

for (int j = 0; j < n; j++) {

long newLen = dist[i][k];

newLen += dist[k][j];

if (newLen < dist[i][j]) {

dist[i][j] = newLen;

pred[i][j] = pred[k][j];

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