Graph Magics

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 Floyd-Warshall 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.


# 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 ]
    End If
End ReconstructPath

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.

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