Floyd-Warshall Algorithm—All Paths, All at Once

Shreyas Naphad
Jul 5
1 min read

Updated: Jul 8

Imagine you’re building a global travel app 🌍. You don’t just want the shortest route from A to B—you want the shortest path between every pair of cities.

Floyd-Warshall does exactly that. It finds all-pairs shortest paths in a graph.

🧠 What’s the Core Idea?

Try every possible intermediate node between each pair of cities. If passing through that node gives a shorter route, update the distance.

🛠️ How It Works

Start with a matrix that stores distances between all nodes.
For each node k (as an intermediate stop), update the distance from i to j like this: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Repeat for all combinations of i, j, and k.

✈️ Real-Life Analogy

Think of all cities connected by flights. You ask, “If I stop over at City K, is it cheaper to go from City I to City J?” If yes, update your app with the new route. You do this for every possible stopover—smart, right?