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:
- No intermediate nodes
- One intermediate
- Two intermediates
- ...
- All nodes
By the end, all possible paths have been considered.