Floyd-Warshall's Algorithm C++: Story

[MyrinNew]

🌌 The Conclave of All Roads — The Floyd-Warshall Chronicles

"In the Age of a Thousand Paths, no traveler could truly know the shortest road until every rumor was tested against every road, from every land to every land."

— Annals of the Great Cartographer

🏰 The World Before Maps

The world was vast — n kingdoms scattered across valleys, mountains, and rivers.

Every kingdom knew of the others, but only through fragmented tales of roads:

• "From my town to yours, it takes 5 days."
• "I heard that through the mountain pass via K, it might be faster."

But no one truly knew the best way to travel from every kingdom to every other kingdom.


So the High Conclave of the Great Mapmakers convened to settle the matter once and for all.


They would compare every pair of kingdoms (i, j) — but in a methodical, almost mystical way.





📜 The Sacred Ledger of Distances





#include
#include
#include
using namespace std;

const int INF = 1e9;







The Mapmakers first declared:

Any road unknown shall be called Infinite.

If no known path exists, they record INF — a polite way of saying:

"Impossible to travel… unless fate changes."

🗺️ The Conclave Hall





class Graph {
int n;
vectorvectorint>> dist;
public:
Graph(int n) : n(n) {
dist.assign(n, vectorint>(n, INF));
for (int i = 0; i n; i++)
dist[i][i] = 0; // Zero distance to self
}







The Great Hall of the Mapmakers is square — n by n tables.

On table (i, j) lies the current known shortest distance from Kingdom i to Kingdom j.


At the start:

• 0 for traveling to oneself.
• INF for unknown paths.
• Any known road will be filled in.

🚪 Carving Known Roads





void addEdge(int u, int v, int w) {
dist[u][v] = w; // Direct known road
}







Whenever a messenger brings news —

"There is a direct road from U to V, taking W days" —

the scribes write it directly into the ledger.


No arguments. This is the truth… for now.





🔮 The Threefold Ritual





void floydWarshall() {
for (int k = 0; k n; k++) {
for (int i = 0; i n; i++) {
for (int j = 0; j n; j++) {
if (dist[i][k] INF && dist[k][j] INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}







The Conclave begins the Threefold Ritual:

1. Outer Loop — The Gatekeeper k:
   
   Imagine opening the gates of one kingdom k at a time and asking:
   
   "If we allowed travelers to pass through k, could we improve any journey?"
   
   That’s why k is outermost — it represents the "current allowed checkpoint" the mapmakers are testing.
2. Middle Loop — The Start i:
   
   For each starting kingdom i, they ask:
   
   "What if we start here, and travel through k?"
3. Inner Loop — The End j:
   
   For each destination j, they check:
   
   "Would going i → k → j be shorter than our currently recorded i → j?"

They test all combinations, like a council testing every rumor, every gossip, every possible detour through k.


If dist[i][k] + dist[k][j] is better than the existing dist[i][j], they update it.

The scroll is rewritten — history is changed.





📖 The Final Map





void printDistances() {
for (int i = 0; i n; i++) {
for (int j = 0; j n; j++) {
if (dist[i][j] == INF) cout "INF ";
else cout dist[i][j] " ";
}
cout "\n";
}
}
};







At the end of the ritual, the scribes unroll the grand map:

• If it says a number, that’s the fastest possible journey known.
• If it says INF, the kingdoms are separated by oceans of impossibility.

🧪 The Day of Truth





int main() {
Graph g(4);
g.addEdge(0, 1, 5);
g.addEdge(0, 3, 10);
g.addEdge(1, 2, 3);
g.addEdge(2, 3, 1);

g.floydWarshall();
g.printDistances();
}







They begin with four kingdoms, connected by partial roads.


The ritual begins:

• First, open the gates of Kingdom 0 (k=0), test all paths.
• Then open Kingdom 1 (k=1), test again.
• Continue until every kingdom has been the “through point” once.

By the end, no rumor remains unchecked.

The shortest path from everywhere to everywhere is known, and the Age of Uncertainty ends.





⚡ Why You’ll Remember This

• k outermost — because you pick one kingdom at a time to act as an allowed "middle stop" for all pairs.
• i middle — starting point.
• j innermost — ending point.
• The process is like gradually lifting travel bans on kingdoms one by one and checking if that unlocks shorter routes.

When you’re in an interview and they ask about Floyd-Warshall, picture the Conclave:

the giant n×n hall of tables, the Threefold Ritual, the Gatekeeper k,

and the slow unveiling of the true, final map of the world.




More...