Graph Magics



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:
  1. 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.

  2. 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.

 
Copyright 2004-2017 Dumitru Ciubatii. All rights reserved.
Protected by copyright laws and international treaties.