Floyd–Warshall Algorithm Explained

Floyd–Warshall Algorithm

Floyd–Warshall is an algorithm used to find the minimum cost between every pair of nodes in a graph.

In our problem:

• Each letter (a–z) is a node
• Each allowed transformation is a directed edge
• The edge has a cost

1. Think of Letters as Cities

Imagine each letter is a city and transformations are one-way roads with tolls.

c → e (1)
e → b (2)
c → b (5)
        

Even though there is a direct road from c → b, it may be cheaper to go via another city.

2. Distance Table

We create a table where:

dist[i][j] = minimum cost to go from i to j
        

Initial rules:

• dist[i][i] = 0
• Direct transformation → given cost
• No transformation → infinity (∞)

From \ To	a	b	c	e
a	0	2	∞	∞
b	∞	0	5	∞
c	∞	5	0	1
e	∞	2	∞	0

3. The Core Idea

Is it cheaper to go directly, or to go via another node?

The key formula:

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

This checks if going from i → k → j is cheaper.

4. Why Three Loops?

for k in nodes:
    for i in nodes:
        for j in nodes:
        

• k → allowed intermediate node
• i → start
• j → destination

At each step, we allow paths that pass through one more intermediate node.

5. Key Example: c → b

Direct cost:

c → b = 5
        

But if we allow e as an intermediate:

c → e → b = 1 + 2 = 3
        

So we update:

dist[c][b] = 3
        

6. Why It Always Works

Floyd–Warshall gradually allows:

1. No intermediate nodes
2. One intermediate
3. Two intermediates
4. ...
5. All nodes

By the end, all possible paths have been considered.

Further Reading

1. Dijkstra’s Algorithm