Shortest Paths between every pair of vertices
Task:
Find shortest paths between every pair of vertices.
Solution:
There is a simple and effective algorithm that solves this task in O(N3). It's well known as
Floyd-Warshall algorithm.
Algorithm:
- Let A be a NxN matrix (N is the number of vertices), A(i,j)
representing the length (or cost) of the shortest path from i to j.
For each element A(i,j) assign a value equal to the cost of the edge going from i
to j, or an infinity value if this edge doesn't exist.
- At each step, for each pair of vertices i and j see if there's an intermediate vertex k
so that the path from i to j through k is shorter than the one already found for i
and j.
If i, j and k are ordered properly, only O(N3)
operations are needed to find the values of all elements of A. Such an order is obtained when first k
is considered and then i and j.
Pseudocode:
# N - number of vertices
# weight(i,j) - weight of the edge from vertex i to j ; equal to infinity if such an edge doesn't exist
For i = 1 to N
For j = 1 to N
A(i,j) = weight(i,j)
For k=1 to N # k is the intermediate vertex
For i=1 to N
For j=1 to N
# check if the path from i to j that passes
through k is shorter then the one already found
If A(i,k) + A(k,j) < A(i,j) Then A(i,j) = A(i,k) + A(k,j)
Complexity:
There are 3 nested cycles each being executed N times, thus the complexity of the algorithm is O(N3).
Extensions:
Besides lengths, it is possible to find out the paths themselves from the above algorithm. This can be done by storing for each pair (i,j)
the vertex k that was used as the intermediate vertex to connect the path from i to j.
Having this, the shortest path from i to j can be reconstructed recursively by finding at each step the
path to the left and to the right of k, and then concatenating them into one single path:
ReconstructPath ( from vertex i to j ) #
finds the path from i to j
If (shortest path from i to j represents the edge between them) Then
Return a path composed of i and j
Else
Let k be the intermediate vertex of the path from i to j
Return the path: [ ReconstructPath(i,k) ] concatenated with [ ReconstructPath(k,j) without
first vertex k ]
End If
End ReconstructPath
Path reconstruction runs in O(N) and thus the complexity of the algorithm is not affected.
Notes:
Floyd-Warshall algorithm works for graphs that contain negative weights as long as there are no negative cycles.
|