Floyd–Warshall Algorithm: All-Pairs Shortest Paths

The Floyd–Warshall algorithm is a dynamic-programming algorithm used to find the shortest paths between every pair of vertices in a weighted directed graph.

Unlike Dijkstra's algorithm, which finds shortest paths from one source vertex to all other vertices, Floyd–Warshall finds shortest paths from every vertex to every other vertex.

1. What is the All-Pairs Shortest-Path Problem?

Consider a weighted directed graph:


       4
   A ------> B
   |         |
  2|         |1
   ↓         ↓
   C ------> D
       3

We may want to know:

shortest path from A to B
shortest path from A to C
shortest path from A to D
shortest path from B to A
shortest path from B to C
...
shortest path between every pair of vertices

This is called the All-Pairs Shortest-Paths (APSP) problem.

The Floyd–Warshall algorithm solves this problem by considering possible intermediate vertices on a path.

2. The Main Idea of Floyd–Warshall

The easiest way to understand Floyd–Warshall is:

For every pair of vertices i and j, ask whether going through another vertex k gives a shorter path.

Suppose we currently know the shortest distance from:


i → j

Now consider another vertex k.

There are two possibilities:

Option 1: Do not go through k


i ----------------→ j

Cost:


D[i][j]

Option 2: Go through k


i ----→ k ----→ j

Cost:


D[i][k] + D[k][j]

Therefore, we simply choose the smaller:


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

This single equation is the heart of the Floyd–Warshall algorithm.

3. Why "Intermediate Vertices"?

This is the important dynamic-programming idea used in CLRS.

Number the vertices:


1, 2, 3, ..., n

Suppose we are considering paths from vertex i to vertex j.

Initially, we allow no intermediate vertices.

Then we allow vertex 1 as an intermediate vertex.

Then:


1, 2

Then:


1, 2, 3

and so on.

Finally, we allow:


1, 2, 3, ..., n

as intermediate vertices.

The formulation defines:

dij(k)

as the shortest-path distance from i to j when only vertices:

{1,2,…,k}

are allowed as intermediate vertices.

4. Starting Condition

When:

$k = 0$

we don't allow any intermediate vertices.

Therefore, the path from i to j can contain:

the direct edge (i,j), or
no path at all.

So initially:

$d_{ij (0)} = w_{ij}$

where w[i][j] is the weight of the direct edge from i to j.

For example:


W =

0    3    8    ∞
∞    0    2    5
∞    ∞    0    1
∞    ∞    ∞    0

Here:

0 means distance from a vertex to itself.
3 means there is a direct edge with weight 3.
∞ means there is no direct edge.

5. The Recurrence Relation

Now suppose we allow vertex k as an intermediate vertex.

For a path from i to j, there are two possibilities.

Case 1: The shortest path does not use k

Then the answer remains:

Case 2: The shortest path uses k

The path becomes:

$i \to k \to j$

Therefore, its cost is:

We choose the smaller of the two:

This is the fundamental recurrence of Floyd–Warshall.

6. Simple Example Step-by-Step

Consider three vertices:


A → B = 4
B → C = 3
A → C = 10

Initial distance matrix:


       A    B    C
A      0    4   10
B      ∞    0    3
C      ∞    ∞    0

Allow A as an intermediate

Nothing useful changes.

Allow B as an intermediate

For A → C:

Current:

D [A] [C] = 10

Through B:

D [A] [B] + D [B] [C]

= 4 + 3 = 7

Therefore:

D [A] [C] = min (10, 7) = 7

New matrix:


       A    B    C
A      0    4    7
B      ∞    0    3
C      ∞    ∞    0

We have discovered a shorter path:


A → B → C

with total cost:

7

7. Floyd–Warshall Algorithm

8. Understanding the Three Loops

Students often find the three loops confusing.

Think of them this way:

Outer loop: `k`


for k = 1 to n

Which intermediate vertex am I considering?

Middle loop: `i`


for i = 1 to n

From which vertex am I starting?

Inner loop: `j`


for j = 1 to n

To which vertex am I going?

So:


k → intermediate vertex
i → source vertex
j → destination vertex

At every step we ask:

Is going from i to k to j cheaper than going directly from i to j using the best distance known so far?

9. Why Does Dynamic Programming Work?

Floyd–Warshall has the two important properties needed for dynamic programming.

1. Optimal Substructure

Suppose the shortest path from i to j goes through k:


i → ... → k → ... → j

Then the portions:


i → ... → k

and


k → ... → j

must themselves be shortest paths under the corresponding restrictions.

Otherwise, we could replace one portion with a shorter path and obtain a shorter path from i to j.

This is the optimal-substructure property used by Floyd–Warshall.

2. Overlapping Subproblems

When calculating shortest paths for many different pairs, the same smaller shortest-path problems occur repeatedly.

Instead of solving them again, Floyd–Warshall stores their results in the distance matrix.

Thus, each stage builds on the results of the previous stage.

10. How the Distance Matrix Changes

Suppose we start with:


D(0)

where only direct edges are considered.

Then:


D(1)

allows vertex 1 as an intermediate.

Then:


D(2)

allows vertices 1 and 2.

Then:


D(3)

allows vertices 1, 2 and 3.

...

Finally:


D(n)

allows every vertex as an intermediate.

Therefore:

D(n)

contains the shortest distances between every pair of vertices.

11. Example

Consider:


A → B = 3
A → C = 8
B → C = 1
C → A = 2

Initially:


       A    B    C
A      0    3    8
B      ∞    0    1
C      2    ∞    0

Now Floyd–Warshall considers each vertex as an intermediate.

For example, when B is the intermediate vertex:


A → B → C

has cost:

$3 + 1 = 4$

which is better than:

$A \to C = 8$

Therefore:

$D [A] [C] = 4$

Similarly, other pairs are checked.

The important point is that we don't manually identify which paths to try. The three nested loops systematically check every possibility.

12. Floyd–Warshall vs. Dijkstra

This is a useful comparison for students.

Feature	Dijkstra	Floyd–Warshall
Problem	Single-source shortest paths	All-pairs shortest paths
Source	One source	Every vertex
Technique	Greedy	Dynamic programming
Main data structure	Min-priority queue	Distance matrix
Negative edges	Not allowed	Can handle negative edges, provided there are no negative cycles
Typical representation	Adjacency list	Matrix
Time	Depends on implementation	Θ(V³)

13. Complexity Analysis

This is one of the easiest complexity analyses to explain.

The algorithm has three nested loops:


for k = 1 to n          → n times

    for i = 1 to n      → n times

        for j = 1 to n  → n times

Therefore, the total number of executions of the main statement is:

$n \times n \times n$ $= n^{3}$

Each execution performs only a constant amount of work:


D[i][k] + D[k][j]

and


min(...)

Both take:

O(1)

time.

Therefore:

T(n)=Θ(n^3)

14. Space Complexity

The algorithm works with an:

$n \times n$

distance matrix.

Therefore, the space required is:

Θ(n^2)

If separate matrices D(0),D(1),…,D(n) are maintained, more space is needed. However, the practical implementation can update a single matrix in place, reducing the working space to:

Θ(n^2)

15. Constructing the Actual Shortest Paths

The distance matrix tells us the shortest distance, but sometimes we also need the actual path.

For example, knowing:

$D [A] [D] = 7$

is useful, but we may also want:


A → B → C → D

To reconstruct paths, Floyd–Warshall can maintain an additional predecessor matrix.

The following algorithm describes maintaining a sequence of predecessor matrices along with the distance matrices.

So we can maintain:


D[i][j] → shortest distance from i to j

Π[i][j] → predecessor information for reconstructing the path

Predecessor Matrix

For every pair (i,j), define:

Π[i][j]

as:

The predecessor of vertex j on a shortest path from vertex i to vertex j.

During Floyd–Warshall, actually considers a sequence of predecessor matrices:

where:

is the final predecessor matrix.

The important idea is that:

stores the predecessor of j on a shortest path from i to j whose intermediate vertices are restricted to:

{1,2,…,k}

Initial Predecessor Matrix

Initially:

k = 0

No intermediate vertices are allowed.

Therefore, the only possible path from i to j is the direct edge (i,j).

So :

Why?

Suppose we have:


A ─────→ B

Then the predecessor of B on the path from A to B is simply:

Therefore:

Π [A] [B] = A

If there is no edge:


A       B

then there is no path yet, so:

Π [A] [B] = N I L

For a vertex itself:

Π [A] [A] = N I L

What Happens During Floyd-Warshall? Recall the Floyd-Warshall distance update: There are two possibilities. Case 1: The path does NOT improve through k We have: So the existing shortest path from i to j remains the best. Therefore: In simple words: The shortest path didn't change, so its predecessor doesn't change. Case 2: The Path Improves Through k Suppose: Then we have found a shorter path: i \to ... \to k \to ... \to j The question is: What is the predecessor of j now? The answer is: Use the same predecessor of j that occurs on the shortest path from k to j . Therefore:

16.How to Incorporate It Into Floyd–Warshall

We can modify the normal Floyd–Warshall algorithm.

Distance matrix


D[i][j]

stores the shortest distance.

Predecessor matrix


Π[i][j]

stores the predecessor of j.

The algorithm becomes:


FLOYD-WARSHALL(W)

D = W

for i = 1 to n
    for j = 1 to n
        if i == j or W[i][j] == ∞
            Π[i][j] = NIL
        else
            Π[i][j] = i

for k = 1 to n
    for i = 1 to n
        for j = 1 to n

            if D[i][k] + D[k][j] < D[i][j]

                D[i][j] =
                    D[i][k] + D[k][j]

                Π[i][j] =
                    Π[k][j]

return D, Π

The important additional line is:


Π[i][j] = Π[k][j]

17.Constructing the Predecessor Graph

After Floyd–Warshall finishes, we have the final predecessor matrix:

Π = Π^{(n)}

Now we can construct a predecessor graph for each source vertex.

For a fixed source vertex i, consider every reachable vertex j.

The matrix gives:

Π[i][j]

which tells us the predecessor of j on a shortest path from i to j.

Therefore, create an edge:

(Π[i][j],j)

for every reachable j.

Example of a Predecessor Graph

Suppose the final predecessor row for source A is:

Destination	B	C	D	E
Predecessor	A	B	C	C

Then we have:


A → B
B → C
C → D
C → E

Therefore, the predecessor graph rooted at A is:

This represents shortest paths from A.

For example:

Shortest path A → D

Follow predecessors backward:


D
↓
C
↓
B
↓
A

Reverse:


A → B → C → D

Shortest path A → E


E
↓
C
↓
B
↓
A

Reverse:


A → B → C → E

One Predecessor Graph for Each Source

This is an important distinction.

Floyd–Warshall solves all-pairs shortest paths.

Therefore, for every source i, we can construct a shortest-path tree rooted at i.

For example:


Source A:

        A
        |
        B
       / \
      C   D

and for another source:


Source B:

        B
       / \
      A   C
           \
            D

The exact structure depends on the graph and shortest paths.

So conceptually:

One predecessor tree for each source vertex

17.Example

Consider the wighted graph

18. Applications of Floyd–Warshall

Floyd–Warshall is particularly useful when we need shortest paths between many or all pairs of vertices.

Applications include:

🛣️ Transportation and Road Networks

Finding the shortest travel distance between every pair of cities.

🌐 Computer Networks

Finding minimum-cost paths between every pair of network nodes.

🚚 Logistics

Determining the minimum transportation cost between every pair of warehouses, distribution centers, or cities.

🗺️ Navigation Systems

Precomputing distances between locations when the graph is relatively small or moderate in size.

📡 Communication Networks

Finding minimum-cost routes between network devices.

🔗 Graph Analysis

It can also be used to determine reachability information and, with suitable modifications, compute the transitive closure of a directed graph.

18. Important Limitation

The standard Floyd–Warshall algorithm can work with negative edge weights, unlike Dijkstra's algorithm.

For example:


A → B = 4
B → C = -2

is acceptable.

However, negative-weight cycles require special consideration because a shortest path may then be undefined: repeatedly traversing the negative cycle can make the path cost smaller and smaller.

A useful observation in Floyd–Warshall is that if, after the algorithm finishes,

$D [i] [i] < 0$

for some vertex i, then the graph contains a negative-weight cycle reachable in the relevant formulation.

19.Summary

You can explain Floyd–Warshall to undergraduate students in these words:

Floyd–Warshall is a dynamic-programming algorithm for finding the shortest paths between every pair of vertices in a weighted graph. It maintains a distance matrix. For every pair of vertices i and j, it checks whether the path through an intermediate vertex k is shorter than the currently known path. The update is D[i][j] = min(D[i][j], D[i][k] + D[k][j]). The algorithm considers vertices one by one as possible intermediate vertices. After all vertices have been considered, the matrix contains the shortest distances between every pair of vertices.

Key points to remember

Concept	Floyd–Warshall
Technique	Dynamic Programming
Problem	All-Pairs Shortest Paths
Main idea	Try every vertex as an intermediate vertex
Recurrence	$D [i] [j] = min (D [i] [j], D [i] [k] + D [k] [j])$
Data structure	Distance matrix
Time	Θ(n³)
Space	Θ(n²)
Negative edges	Yes
Negative cycles	Cannot have a well-defined shortest path

The most important line for students to remember is:

New path through k=D[i][k]+D[k][j]

and then:

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

That single recurrence captures the central idea of the Floyd–Warshall algorithm.