19.8. All-Pairs Shortest Paths¶
We next consider the problem of finding the shortest distance between all pairs of vertices in the graph, called the all-pairs shortest paths problem. To be precise, for every \(u, v \in \mathbf{V}\), calculate \(d(u, v)\).
One solution is to run Dijkstra’s algorithm
for finding the shortest path
\(|\mathbf{V}|\) times, each
time computing the shortest path from a different start vertex.
If \(\mathbf{G}\) is sparse
(that is, \(|\mathbf{E}| = \Theta(|\mathbf{V}|)\))
then this is a good solution, because the total cost will be
\(\Theta(|\mathbf{V}|^2 + |\mathbf{V}||\mathbf{E}| \log
|\mathbf{V}|) = \Theta(|\mathbf{V}|^2 \log |\mathbf{V}|)\)
for the version of Dijkstra’s algorithm based on priority queues.
For a dense graph, the priority queue version of Dijkstra’s algorithm
yields a cost of \(\Theta(|\mathbf{V}|^3 \log |\mathbf{V}|)\),
but the version using MinVertex
yields a cost
of \(\Theta(|\mathbf{V}|^3)\).
Another solution that limits processing time to \(\Theta(|\mathbf{V}|^3)\) regardless of the number of edges is known as Floyd’s algorithm. It is an example of dynamic programming. The chief problem with solving this problem is organizing the search process so that we do not repeatedly solve the same subproblems. We will do this organization through the use of the \(k\)-path. Define a k-path from vertex \(v\) to vertex \(u\) to be any path whose intermediate vertices (aside from \(v\) and \(u\)) all have indices less than \(k\). A 0-path is defined to be a direct edge from \(v\) to \(u\). Figure illustrates the concept of \(k\)-paths.
Define \({\rm D}_k(v, u)\) to be the length of the shortest
\(k\)-path from vertex \(v\) to vertex \(u\).
Assume that we already know the shortest \(k\)-path from \(v\)
to \(u\).
The shortest \((k+1)\)-path either goes through vertex \(k\)
or it does not.
If it does go through \(k\), then the best path is
the best \(k\)-path from \(v\) to \(k\) followed by the
best \(k\)-path from \(k\) to \(u\).
Otherwise, we should keep the best \(k\)-path seen before.
Floyd’s algorithm simply checks all of the possibilities in a triple
loop.
Here is the implementation for Floyd’s algorithm.
At the end of the algorithm, array D
stores the all-pairs shortest
distances.
/** Compute all-pairs shortest paths */
static void Floyd(Graph G, int[][] D) {
for (int i=0; i<G.n(); i++) { // Initialize D with weights
for (int j=0; j<G.n(); j++) {
if (G.weight(i, j) != 0) { D[i][j] = G.weight(i, j); }
}
}
for (int k=0; k<G.n(); k++) { // Compute all k paths
for (int i=0; i<G.n(); i++) {
for (int j=0; j<G.n(); j++) {
if ((D[i][k] != Integer.MAX_VALUE) &&
(D[k][j] != Integer.MAX_VALUE) &&
(D[i][j] > (D[i][k] + D[k][j])))
{
D[i][j] = D[i][k] + D[k][j];
}
}
}
}
}
Clearly this algorithm requires \(\Theta(|\mathbf{V}|^3)\) running time, and it is the best choice for dense graphs because it is (relatively) fast and easy to implement.