(^168) | Chapter 6: Graph Algorithms
FLOYD-WARSHALL computes adist[i][j] matrix that stores the resulting
computations of the shortest path fromvitovjin the weighted, directed graph;
along the way, it computes apred[i][j]matrix to be used to reconstruct an actual
shortest path between two vertices. The simple function shown in Example 6-8
constructs an actual shortest path (there may be more than one) from a givenvsto
vt. It works by recovering predecessor information from thepred matrix.
Analysis
The time taken by FLOYD-WARSHALLis dictated by the number of times the
minimization function is computed, which is O(V^3 ), as can be seen from the three
nested loops. TheconstructShortestPathfunction in Example 6-8 executes in
O(E) since the shortest path might include every edge in the graph.
}
}
}
}
}
Example 6-8. Code to recover shortest path from the computed pred[][]
/**
- Output path as vector of vertices from s to t given the pred results
- from an allPairsShortest execution. Note that s and t must be valid
- integer vertex identifiers. If no path is found between s and t, then an
- empty path is returned.
/
void constructShortestPath(int s, int t, / in /
vector< vector> const &pred, / in /
list&path) { / out */
path.clear( );
if (t < 0 || t >= (int) pred.size( ) || s < 0 || s >= (int) pred.size( )) {
return;
}
// construct path until we hit source 's' or -1 if there is no path.
path.push_front(t);
while (t != s) {
t = pred[s][t];
if (t == -1) { path.clear( ); return; }
path.push_front(t);
}
}
Example 6-7. Floyd-Warshall algorithm for computing all pairs shortest path (continued)
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