Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a dynamic programming algorithm for finding the shortest paths between every pair of vertices in a graph. Robert Floyd and Stephen Warshall published it independently in 1962. Unlike Dijkstra’s and Bellman-Ford algorithms, it computes all-pairs shortest paths in a single run. With O(V³) time complexity, it can handle negative edge weights and detect negative cycles, making it useful for tasks such as network diameter calculation, transitive closure, and database query optimization.

History of the Floyd-Warshall Algorithm

What is the Floyd-Warshall Algorithm?

A dynamic programming-based algorithm that simultaneously finds the shortest paths between all pairs of vertices in a weighted graph, capable of handling negative weight edges and detecting the presence of negative cycles.

American computer scientist Robert W. Floyd introduced the algorithm in his 1962 Communications of the ACM paper “Algorithm 97: Shortest Path,” where he applied it to the shortest path problem. In the same year, Stephen Warshall published “A Theorem on Boolean Matrices” in the Journal of the ACM, presenting the same idea for the transitive closure problem. The algorithm was named after both researchers. French mathematician Bernard Roy had already described essentially the same method in 1959, so some European literature refers to it as the “Roy-Floyd-Warshall algorithm.”

This algorithm is a classic example of dynamic programming frequently covered in computer science education and has made significant contributions to the development of graph theory and optimization theory. Robert Floyd received the Turing Award in 1978 for his contributions to programming languages and algorithms, including this algorithm. In modern computer science, the algorithm is practically utilized in various fields including network routing, reachability analysis in game theory, relational operations in databases, and connectivity analysis in social networks.

How the Algorithm Works

The core idea of the Floyd-Warshall algorithm is the concept of “intermediate vertices,” progressively computing the shortest path from i to j using only vertices from the set {1, 2, …, k} as intermediate vertices.

Dynamic Programming Recurrence Relation

Core Recurrence Relation

D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j])

When vertices 1 through k can be used as intermediate vertices, the shortest distance from i to j is the shorter of (1) the path not passing through k and (2) the path passing through k.

In actual implementation, a 2D array is used instead of a 3D array for space optimization. This is safe because at the k-th stage, the values D[i][k] and D[k][j] are identical to the values of paths that do not use k as an intermediate vertex.

D[i][j] = min(D[i][j], D[i][k] + D[k][j])

This recurrence relation captures a simple idea: update the distance if going through vertex k produces a shorter path. It relies on the optimal substructure property, where subpaths of shortest paths are themselves shortest paths.

Meaning of the Triple Loop

The algorithm structure consists of three nested loops, and the role and order of each loop are crucial to correctness.

Outermost loop (k): Sequentially selects intermediate vertices from 1 to V. At the k-th iteration, only vertices {1, 2, …, k} are considered as intermediate vertices. As k increases, paths using more intermediate vertices are explored, progressively reaching the optimal solution.

Middle loop (i): Iterates through starting vertices from 1 to V.

Innermost loop (j): Iterates through destination vertices from 1 to V.

The loop order being k → i → j is essential. If k were in the innermost position, the algorithm would not work correctly. k must be outermost to ensure the progressive expansion of dynamic programming, where the k-th stage uses results from up to the (k-1)-th stage.

Algorithm Execution Steps

Step 1: Initialization

Create a V × V 2D array D. Initialize adjacent vertices with edge weights, set unconnected vertices to infinity (INF), and set the distance to self D[i][i] to 0.

Step 2: Execute Triple Loop

Iterate intermediate vertex k from 1 to V, applying D[i][j] = min(D[i][j], D[i][k] + D[k][j]) for all (i, j) pairs.

Step 3: Check Results

After the algorithm terminates, D[i][j] contains the shortest distance from vertex i to vertex j. If a negative cycle exists, one or more diagonal entries will satisfy D[i][i] < 0.

Working Example

Assume we have the following graph.

Vertices: 1, 2, 3, 4
Edges: 1→2(3), 1→3(8), 1→4(∞), 2→3(2), 2→4(5), 3→4(1)

Initial distance matrix:

    1    2    3    4
1 [ 0    3    8    ∞  ]
2 [ ∞    0    2    5  ]
3 [ ∞    ∞    0    1  ]
4 [ ∞    ∞    ∞    0  ]

After k=1 (considering vertex 1 as intermediate): No change

After k=2 (considering vertices 1, 2 as intermediate):

• D[1][3] = min(8, 3+2) = 5 (1→2→3)
• D[1][4] = min(∞, 3+5) = 8 (1→2→4)

After k=3 (considering vertices 1, 2, 3 as intermediate):

• D[1][4] = min(8, 5+1) = 6 (1→2→3→4)
• D[2][4] = min(5, 2+1) = 3 (2→3→4)

Final result:

    1    2    3    4
1 [ 0    3    5    6  ]
2 [ ∞    0    2    3  ]
3 [ ∞    ∞    0    1  ]
4 [ ∞    ∞    ∞    0  ]

Implementation Example

Here is a C++ implementation of the Floyd-Warshall algorithm.

#include <iostream>
#include <vector>
using namespace std;

#define INF 1e9

int main() {
    int n, m; // n: number of vertices, m: number of edges
    cin >> n >> m;

    // Initialize distance matrix
    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));

    for (int i = 1; i <= n; i++) {
        dist[i][i] = 0; // Distance to self is 0
    }

    // Edge input
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], (long long)c); // Handle duplicate edges
    }

    // Floyd-Warshall algorithm
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // Negative cycle check
    bool hasNegativeCycle = false;
    for (int i = 1; i <= n; i++) {
        if (dist[i][i] < 0) {
            hasNegativeCycle = true;
            break;
        }
    }

    if (hasNegativeCycle) {
        cout << "A negative cycle exists." << '\n';
    } else {
        // Output results
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] == INF) {
                    cout << "INF ";
                } else {
                    cout << dist[i][j] << ' ';
                }
            }
            cout << '\n';
        }
    }

    return 0;
}

Code Explanation

• dist: A V × V 2D array where dist[i][j] stores the shortest distance from vertex i to j.
• dist[i][i] = 0: Distance to self must always be initialized to 0. Omitting this leads to incorrect results.
• dist[i][k] != INF && dist[k][j] != INF condition: Checks before performing addition with INF to prevent overflow.
• Duplicate edge handling: Multiple edges for the same (a, b) pair may be given, so the minimum value is selected.

Negative Weights and Negative Cycles

Unlike Dijkstra’s algorithm, the Floyd-Warshall algorithm can correctly handle edges with negative weights. This is because, due to the nature of dynamic programming, it systematically explores all possible paths.

Meaning of Negative Cycles

What is a Negative Cycle?

A cycle where the sum of the weights of its constituent edges is negative. If a negative cycle exists, the distance can be reduced to negative infinity by repeating the cycle infinitely, so the shortest path is not defined.

For example, if the sum of weights on a path A → B → C → A is -5, the distance continues to decrease as -5, -10, -15, … as the cycle repeats. In such cases, shortest distances involving that cycle are not well defined because the total cost can be driven downward without bound.

Negative Cycle Detection Method

Negative cycles can be detected in O(V) time by examining the diagonal elements after running the Floyd-Warshall algorithm. Normally, the shortest distance D[i][i] back to oneself should always be 0. However, if a negative cycle exists, vertices with D[i][i] < 0 are found. Such a vertex i is either included in a negative cycle or can reach a negative cycle.

Real-World Applications of Negative Cycles

Negative cycles are utilized in arbitrage detection in financial trading. When modeling exchange rates between multiple currencies as a graph, transforming an exchange rate r to -log(r) turns repeated multiplication of exchange rates into addition. The existence of a negative cycle indicates an arbitrage opportunity to gain risk-free profit by repeating exchanges.

Time Complexity Analysis

The time complexity of the Floyd-Warshall algorithm is O(V³), where V is the number of vertices.

Detailed O(V³) Analysis

Each loop of the triple nested loop executes V times, so a total of V × V × V = V³ comparison and update operations are performed. Each operation consists of addition, comparison, and minimum value selection, performed in constant time O(1). Space complexity is O(V²), requiring a V × V 2D array. Even with an additional next array for path reconstruction, it remains O(V²).

Practical Limits

On modern computers, V up to about 500 can be processed within 1 second. When V exceeds 1,000, execution time increases rapidly, and other algorithms should be considered for large-scale graphs.

Comparison with Other Shortest Path Algorithms

Algorithm Selection Guide

• All-pairs shortest paths, dense graph: Floyd-Warshall algorithm
• All-pairs shortest paths, sparse graph, positive weights only: Run Dijkstra V times
• Single-source shortest path: Dijkstra or Bellman-Ford
• Negative weights, negative cycle detection needed: Floyd-Warshall or Bellman-Ford
• Simple implementation preferred, small number of vertices: Floyd-Warshall algorithm

Path Reconstruction

In many cases, not only the shortest distance but also the actual path needs to be reconstructed. For this purpose, a next array is used.

#include <iostream>
#include <vector>
using namespace std;

#define INF 1e9

void printPath(int i, int j, vector<vector<int>>& next) {
    if (next[i][j] == -1) {
        cout << "No path" << '\n';
        return;
    }

    cout << i;
    while (i != j) {
        i = next[i][j];
        cout << " -> " << i;
    }
    cout << '\n';
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));
    vector<vector<int>> next(n + 1, vector<int>(n + 1, -1));

    for (int i = 1; i <= n; i++) {
        dist[i][i] = 0;
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (c < dist[a][b]) {
            dist[a][b] = c;
            next[a][b] = b; // Initialize with directly connected vertex
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k]; // First vertex to visit when going from i to j
                }
            }
        }
    }

    // Print path from 1 to n
    printPath(1, n, next);

    return 0;
}

next[i][j] stores the vertex visited immediately after i on the shortest path from i to j. Whenever the distance is updated, next is also updated. When printing the path, follow next to sequentially list all intermediate vertices.

Real-World Applications

The Floyd-Warshall algorithm is used as a core component in various real-world problems.

Transitive Closure

Transitive closure is the problem of determining whether vertex j is “reachable” from vertex i in a graph, checking only connectivity while ignoring weights. The Warshall algorithm, a variant of Floyd-Warshall, solves this problem using boolean operations. It is utilized in database relationship analysis (e.g., “Is A an ancestor of B?”), control flow reachability in program analysis, and compiler optimization.

Network Diameter Calculation

The maximum of all shortest distances between vertex pairs is the network’s diameter, which is a key indicator for evaluating network efficiency and vulnerabilities. In communication networks, it represents the worst-case transmission delay. In social network analysis, it is used to calculate the distance between “the two most distant people” (e.g., Six Degrees of Separation).

Transportation Network Optimization Between Cities

Precomputing shortest paths between every pair of cities helps with logistics center placement, prioritizing transportation infrastructure investment, and optimizing emergency service deployment. In small-scale networks with limited vertex counts, Floyd-Warshall can precompute all paths and answer queries in O(1) time.

Game AI Pathfinding

When game maps are sufficiently small (e.g., sectors in grid-based strategy games), pre-calculating all-pairs shortest paths enables fast pathfinding at runtime. This provides much faster response times than running the A* algorithm each time and is an effective optimization strategy when memory constraints permit.

Optimization Techniques

Space Optimization

Space can be reduced from O(V³) to O(V²) by reusing a 2D array D[i][j] instead of a 3D array D[k][i][j]. This is safe because at the k-th stage, D[i][k] and D[k][j] are identical to the (k-1)-th results.

Parallel Processing

Updates for all (i, j) pairs at each k stage are independent of each other and can be parallelized. Using GPUs or multi-core CPUs to process the inner two loops in parallel can achieve significant speed improvements, which is an important technique for achieving practical performance in large-scale graphs.

Early Termination

If no distances are updated at a particular k stage, no updates will occur in subsequent stages either, so the algorithm can be terminated. However, this check itself costs O(V²), so it is not always advantageous. In practice, its effectiveness varies depending on graph characteristics.

Implementation Considerations

• INF value selection: Choose a value large enough but with room so that INF + INF does not overflow. For int range, 1e9 is appropriate; for long long range, around 1e18/2 is suitable.
• Self-distance initialization: Omitting D[i][i] = 0 leads to incorrect results, so initialization is mandatory.
• Duplicate edge handling: Multiple edges may be given for the same (a, b) pair, so the minimum value must be selected.
• Undirected graphs: Represent as bidirectional edges; both (a, b) and (b, a) must be added.
• Path reconstruction: If needed, maintain the next array from the start; it is difficult to add later.

Conclusion

The Floyd-Warshall algorithm was independently published by Robert Floyd and Stephen Warshall in 1962. Using dynamic programming, it computes shortest paths between all pairs of vertices in O(V³) time. Its combination of simplicity and support for negative weights and negative-cycle detection keeps it relevant in areas such as transitive closure, network diameter calculation, transportation planning, and game AI. It is especially well suited to dense graphs with a few hundred vertices or fewer, where all-pairs shortest paths are needed.