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.

dist[a][b] contains the current shortest distance from a to b. The graph is V vertices, labeled 0 to V-1.

for(int k = 0; k < V; k++)
    for(int i = 0; i < V; i++)
        for(int j = 0; j < V; j++)
            if(dist[i][k] + dist[k][j] < dist[i][j])
                dist[i][j] = dist[i][k] + dist[k][j];
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License