Floyd's [Algorithm] for the [all pairs shortest path] problem is simple and elegant. In [Introduction to Algorithms|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 [vertex|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³)

Floyd's Algorithm (thing)