The all-pairs shortest paths (APSP) problem is to find shortest paths between all pairs of vertices in a graph. There is a simple form for the solution that records a minimal amount of information needed to lookup distances along shortest paths as well as reconstruct the shortest paths.
There are some simple but inefficient algorithms to solve the APSP problem. The Floyd-Warshall agorithm gives a more efficient solution.
For this presentation it is assumed that all edge weights are non-negative.
If the vertices in the graph are identified with integers then the
solution to the APSP problem for the graph can be given in the form of a
pathInfo
matrix.
Each entry pathInfo[i][j]
is an object with two attributes:
This matrix lets us quickly determine the shortest-path distance from a
vertex i to a vertex j.
To find the path itself, you first get
k1 = pathInfo[i][j].neighbor
.
This gives you the first step on the path.
The next step is to k2 = pathInfo[k1][j].neighbor
.
This is repeated until you reach j
.
There are two inefficient ways of solving the APSP:
The Floyd-Warshall algorithm
initialize pathInfo matrix using only paths with no intermediate vertices for each vertex k // Invariant: // For every i and j, pathInfo[i][j] describes the shortest path from // i to j among paths whose intermediate vertices are all less than k. for each vertex i for each vertex j update pathInfo[i][j] to allow for using k as an intermediate vertex end for end for end for
The following is the invariant for the outermost loop:
For every i and j, pathInfo[i][j] describes the shortest path from i to j among paths whose intermediate vertices are all less than k.
Initialization code should be designed to establish the invariant for
k = 0.
In other words, pathInfo[i][j]
initially describes the
shortest path from i to j that has no intermediate vertices.
The paths we are considering have at most one edge.
If i == j
(no edges) then
pathInfo[i][i].distance
should be set to 0
and
pathInfo[i][i].neighbor
should be set to
null
.
If there is an edge of weight w
from vertex i
to vertex j
(one edge) then
pathInfo[i][j].distance
should be set to
w
and
pathInfo[i][j].neighbor
should be set to
j
.
Otherwise
pathInfo[i][j].distance
should be set to
Double.POSITIVE_INFINITY
and
pathInfo[i][j].neighbor
should be set to
null
.
The following is the invariant for the outermost loop:
For every i and j, pathInfo[i][j] describes the shortest path from i to j among paths whose intermediate vertices are all less than k.
Update code assumes the invariant is true for the current value of k. The code should be designed to establish the invariant for k + 1. This ensures that the invariant is true at the beginning of the next iteration of the outermost loop.
The update is suggested by the following diagram.
Here, we are trying to update pathInfo[i][j]
.
If pathInfo[i][j].distance
<
pathInfo[i][k].distance
+
pathInfo[k][j].distance
then allowing k
to be
used as an intermediate vertex yields a shorter path.
Then the update should change pathInfo[i][j]
:
pathInfo[i][j].distance
is set to
pathInfo[i][k].distance + pathInfo[k][j].distance
pathInfo[i][j].neighbor
is set to
pathInfo[i][k].neighbor
Otherwise pathInfo[i][j]
should not be changed.
Note that following these rules does not lead to an update of
either pathInfo[i][k]
or pathInfo[k][j]
.
The loop does not need special case code to deal with these cases.
The Floyd-Warshall run time is O(V^{3}).