Floyd's algorithm uses the dynamic programming method to solve the all-pairs shortest-path problem on a dense graph. The method makes efficient use of an adjacency matrix to solve the problem. Consider an edge-weighted graph , where C(v,w) represents the weight on edge (v,w). Suppose the vertices are numbered from 1 to . That is, let . Furthermore, let be the set comprised of the first k vertices in . That is, , for .
Let be the shortest path from vertex v to w that passes only through vertices in , if such a path exists. That is, the path has the form
Let be the length of path :
Since , the paths are correspond to the edges of G:
Therefore, the path lengths correspond to the weights on the edges of G:
Floyd's algorithm computes the sequence of matrices . The distances in represent paths with intermediate vertices in . Since , we can obtain the distances in from those in by considering only the paths that pass through vertex . Figure illustrates how this is done.
Figure: Calculating in Floyd's algorithm.
For every pair of vertices (v,w), we compare the distance , (which represents the shortest path from v to w that does not pass through ) with the sum (which represents the shortest path from v to w that does pass through ). Thus, is computed as follows: