Shortest Paths between every pair of vertices
Find shortest paths between every pair of vertices.
There is a simple and effective algorithm that solves this task in O(N3). It's well known as
- 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
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.
# 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)
There are 3 nested cycles each being executed N times, thus the complexity of the algorithm is O(N3).
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
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 ]
Path reconstruction runs in O(N) and thus the complexity of the algorithm is not affected.
Floyd-Warshall algorithm works for graphs that contain negative weights as long as there are no negative cycles.