Floyd's Algorithm (thing)

Floyd's Algorithm for the all pairs shortest path problem is simple and elegant. In Cormen et al. book, this is called the Floyd-Warshall algorithm.

Recall that the all pairs shortest path problem is: given a graph, find the shortest path between every pair of vertices in that graph.

The basic notion is that we update an adjacency matrix N times (where N is the number of vertices in the graph). First, we update the graph to reflect the shortest known paths going through node 1. At step 2, we update the graph to reflect the shortest known path going through node 1 or node 2 (or both). At step 3... and so on.

Here's the code:

//Graph g is an adjacency matrix
floyd(Graph g) {
    for(k =0; k < g.size; k++)
        for(i=0; i < g.size; i++)
            for(j=0; j < g.size; j++)
                if(g[i][j] > g[i][k] + g[k][j])
                    g[i][j] = g[i][k] + g[k][j];
}

After running the algorithm, the graph g is transformed such that g[i][j] contains the length of the shortest path from vertex i to vertex j.

Note that for the original adjacency matrix, if there is no edge between two vertices i and j, g[i][j] will have the value infinity. Also in this algorithm, we only store the length of the shortest path, not the path itself. I hope you can see that the algorithm can be easily extended to store the path as well as the length.

Floyd's algorithm runs with a time complexity of O(n³)