Offensive Security Researcher & Quantum Cryptography Analyst

Floyd-Warshall Algorithm: Working, Explanation, and All-Pairs Shortest Paths

Abdul Wahab Junaid
floyd warshall algorithm and working of this algorithm

floyd warshall algorithm and working of this algorithm

Whenever I’ve needed to know the shortest distance between every single pair of nodes in a graph — not just from one starting point, but from all of them to all of them at once — I’ve turned to the Floyd-Warshall algorithm. What draws me to it is its almost deceptive simplicity: a triple-nested loop and one line of comparison inside, yet it solves what seems like it should be a much harder problem. It’s an all-pairs shortest path algorithm, and I find it especially elegant because of how directly the code mirrors the underlying dynamic programming idea, with almost no extra machinery needed.

History and Background

I attribute this algorithm to Robert Floyd, who published it in 1962, building on a related but more general result by Stephen Warshall, who in 1962 had already published an algorithm (Warshall’s algorithm) for computing the transitive closure of a relation. Floyd essentially adapted Warshall’s approach to compute shortest path distances instead of just reachability, which is why the combined method is credited to both names. Interestingly, the same core dynamic programming idea had also been described earlier by Bernard Roy in 1959, so it is occasionally referred to as the Roy-Floyd-Warshall algorithm in some literature, particularly outside the English-speaking world.

Problem Statement

I want to compute the shortest path distance between every pair of vertices in a weighted, directed graph, where edge weights can be negative, but the graph must not contain a negative-weight cycle (a cycle would allow paths to have arbitrarily low cost, making “shortest path” undefined). Running a single-source shortest path algorithm like Dijkstra or Bellman-Ford from every vertex individually would work, but at a higher combined cost in many cases. Floyd-Warshall solves the all-pairs version directly using dynamic programming over intermediate vertices, in a way that’s often simpler to implement than repeating a single-source algorithm many times, especially when the graph is dense.

Core Concepts

How It Works

I proceed by considering, one at a time, whether allowing a new vertex k as an intermediate stop improves any existing shortest path estimate. Concretely:

  1. I initialize dist[i][j] with direct edge weights (or infinity if there’s no direct edge), and dist[i][i] = 0.
  2. For each vertex k from 1 to n (used as a potential intermediate stop), I check for every pair (i, j) whether going through k — i.e., dist[i][k] + dist[k][j] — is shorter than the currently known dist[i][j].
  3. If it is, I update dist[i][j] to this shorter value.
  4. After considering all vertices k as potential intermediates, dist[i][j] holds the true shortest path distance between every pair (i, j).
  5. Optionally, I also check the diagonal dist[i][i] for negative values after the algorithm finishes, which indicates the presence of a negative cycle.

Working Principle

The core mechanism is a very specific form of dynamic programming where I gradually expand the set of vertices allowed as intermediate stops. At each stage k, I’ve already correctly computed the shortest paths using only vertices {1, ..., k-1} as allowed intermediates. Adding vertex k to the allowed set can only help (never hurt), because I always compare the new candidate path against the old value and keep whichever is smaller. This staged expansion guarantees that by the time k reaches n (all vertices considered), every possible intermediate combination has been accounted for, giving the true shortest path over the entire graph.

Mathematical Foundation

I define the DP relation as:

$$ dist_k[i][j] = \min\big(dist_{k-1}[i][j],\ dist_{k-1}[i][k] + dist_{k-1}[k][j]\big) $$

with the base case:

$$ dist_0[i][j] = \begin{cases} 0 & \text{if } i = j \ w(i,j) & \text{if there is an edge from } i \text{ to } j \ \infty & \text{otherwise} \end{cases} $$

After considering all n vertices as intermediates, dist_n[i][j] gives the true shortest path distance between i and j. The total time complexity follows directly from the three nested loops over k, i, and j, each ranging over all n vertices:

$$ T(n) = O(n^3) $$

Diagrams

flowchart TD
    A["Initialize dist matrix with direct edge weights, infinity elsewhere, 0 on diagonal"] --> B["for k = 1 to n"]
    B --> C["for i = 1 to n"]
    C --> D["for j = 1 to n"]
    D --> E{"dist[i][k] + dist[k][j] < dist[i][j]?"}
    E -- Yes --> F["dist[i][j] = dist[i][k] + dist[k][j]"]
    E -- No --> G[Keep current value]
    F --> H{More j?}
    G --> H
    H -- Yes --> D
    H -- No --> I{More i?}
    I -- Yes --> C
    I -- No --> J{More k?}
    J -- Yes --> B
    J -- No --> K["dist matrix now holds all-pairs shortest paths"]

Pseudocode

function floydWarshall(graph, n):
    dist = new n x n matrix

    for i from 1 to n:
        for j from 1 to n:
            if i == j:
                dist[i][j] = 0
            else if edge (i, j) exists:
                dist[i][j] = weight(i, j)
            else:
                dist[i][j] = infinity

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

    for i from 1 to n:
        if dist[i][i] < 0:
            return "Negative cycle detected"

    return dist

Step-by-Step Example

Consider a 4-node graph (A, B, C, D) with directed edges: A->B (3), A->C (8), B->C (2), C->D (1), B->D (7).

Initial dist matrix (using ∞ for no direct edge):

ABCD
A038∞
B∞027
C∞∞01
D∞∞∞0

After considering k = B: dist[A][C] can be updated via A -> B -> C = 3 + 2 = 5, which is better than the direct 8. Also dist[A][D] via A -> B -> D = 3 + 7 = 10.

After considering k = C: dist[A][D] can be updated via A -> C -> D. Using the already-improved dist[A][C] = 5, this gives 5 + 1 = 6, better than the previous 10. Also dist[B][D] via B -> C -> D = 2 + 1 = 3, better than the direct 7.

Final dist matrix:

ABCD
A0356
B∞023
C∞∞01
D∞∞∞0

Time Complexity

Space Complexity

The algorithm requires O(n^2) space to store the distance matrix. If I also want to reconstruct actual shortest paths (not just distances), I need an additional O(n^2) space for the next (successor) matrix used in path reconstruction. The algorithm can be implemented in-place, updating the same matrix throughout, without needing separate matrices for each value of k.

Correctness Analysis

I prove correctness by induction on k, the number of intermediate vertices considered so far. The base case (k = 0) is trivially correct, since dist_0[i][j] is defined directly from the input graph with no intermediates allowed. For the inductive step, I assume dist_{k-1}[i][j] correctly holds the shortest path using only vertices {1, ..., k-1} as intermediates. When considering vertex k, any shortest path from i to j using vertices {1, ..., k} either doesn’t use k at all (in which case its length is already captured by dist_{k-1}[i][j]), or it uses k exactly once as an intermediate stop (since a shortest path never revisits a vertex, assuming no negative cycles), splitting into a path from i to k and from k to j, each of which only uses vertices {1, ..., k-1} as further intermediates by definition. Taking the minimum of these two cases, as the recurrence does, therefore correctly computes dist_k[i][j]. By induction, dist_n[i][j] is correct for all pairs after considering all n vertices.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <limits.h>

#define V 4
#define INF INT_MAX / 2 /* avoid overflow when adding two "infinities" */

void floydWarshall(int graph[V][V]) {
    int dist[V][V];

    /* Initialize distance matrix same as input graph */
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    /* Try every vertex k as an intermediate point */
    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];
                }
            }
        }
    }

    /* Check for negative cycles */
    for (int i = 0; i < V; i++) {
        if (dist[i][i] < 0) {
            printf("Graph contains a negative weight cycle.\n");
            return;
        }
    }

    printf("Shortest distances between every pair of vertices:\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf("%7d", dist[i][j]);
        }
        printf("\n");
    }
}

int main() {
    /* 0=A, 1=B, 2=C, 3=D */
    int graph[V][V] = {
        {0,   3,   8,   INF},
        {INF, 0,   2,   7},
        {INF, INF, 0,   1},
        {INF, INF, INF, 0}
    };

    floydWarshall(graph);
    return 0;
}

Sample Input and Output

Input: the 4-node graph A, B, C, D with edges A->B(3), A->C(8), B->C(2), C->D(1), B->D(7).

Output:

Shortest distances between every pair of vertices:
      0      3      5      6
    INF      0      2      3
    INF    INF      0      1
    INF    INF    INF      0

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version