Floyd-Warshall (FW) Algorithm Tutorial

Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm computes shortest paths between all pairs of vertices in a single run. It handles negative edges but not negative cycles. It's also known as the Roy-Floyd algorithm.

For each intermediate vertex $k$, you check if going through $k$ shortens the path from $i$ to $j$.

function floydWarshall(graph, n):
    dist = n x n matrix
    initialize dist[i][j] = graph[i][j] if edge exists, else infinity
    initialize dist[i][i] = 0

    for k from 0 to n - 1:
        for i from 0 to n - 1:
            for j from 0 to n - 1:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

Loop order: You must iterate $k$ in the outer loop. This ensures paths using vertices $0$ to $k-1$ are computed before considering vertex $k$.

Detecting negative cycles: After completion, check if any $dist[i][i] < 0$. A negative diagonal indicates a negative cycle.

Applications: You use Floyd-Warshall for transitive closure, finding graph diameter, all-pairs shortest paths in dense graphs, and network analysis.

Time complexity: $O(V^3)$ due to three nested loops.

Space complexity: $O(V^2)$ for the distance matrix.