Floyd Warshall

Floyd-Warshall is an all-pairs shortest path algorithm which runs in $O(V^3)$ time. It is a very simple algorithm, requiring only four or five lines in most implementations. It requires a matrix for the distances between two points, so an adjacency matrix is a good choice here. It works by considering optimal paths through a middle vertex. Quite remarkably, if the iteration is done in the correct order, only one iteration is required.

page revision: 2, last edited: 22 Nov 2007 02:30