Floyd–Warshall Algorithm

Overview

Floyd–Warshall is a classic dynamic programming algorithm that computes shortest path distances between every pair of vertices in a weighted directed graph (including negative edge weights) in O(n^3) time. It incrementally improves an n×n distance matrix by allowing intermediate vertices in increasing order. After the main triple loop, a negative value on the diagonal indicates a negative cycle reachable for that vertex.

Core Dynamic Programming Idea

• State: dist_k[i][j] = shortest distance from i to j using only intermediate vertices from the set {1..k}
• Transition: dist_k[i][j] = min(dist_{k-1}[i][j], dist_{k-1}[i][k] + dist_{k-1}[k][j])
• In-Place Optimization: We can reuse a single matrix updating entries as each k becomes available.
• Cycle Detection: Any dist[i][i] < 0 after completion indicates a negative cycle reachable from i.
• Path Reconstruction: Maintain a next[i][j] matrix (successor) updated on improvement.

When to Use

Complexity

The cubic time arises from the triple nested loops over k, i, j. For n ≤ ~400 this can still be practical in educational or moderate analytic contexts. Space is dominated by the distance (and optional next) matrices.

Comparison with Other Shortest Path Algorithms