Bellman-Ford Algorithm C++: Story

⚔️ The Caravan Through the Lands of Shadows — The Bellman-Ford Saga

"In a land where roads could twist in deceit, the fastest path was not always the one that looked shortest…"
— Chronicles of the Desert Traders

🏜️ The Kingdoms of Sand

There were n cities scattered across the desert.
Merchants traveled between them using roads — each road had a toll, sometimes fair, sometimes cruel, and sometimes negative when a generous city paid travelers to pass through.

But the desert was treacherous: some paths would loop forever, endlessly making profit — cursed loops, they called them.
The Guild of Desert Traders needed a way to find the shortest path from a starting city to all others — and to know if any cursed loop existed.

#include <iostream> #include <vector> #include <limits> using namespace std; struct Edge { int u, v, w; }; 

The traders recorded every known road in a scroll of edges:

• u — the city where the road began
• v — the city where it ended
• w — the toll or reward for using it

📜 The Guild Ledger

class BellmanFord { int n; vector<Edge> edges; vector<int> dist; const int INF = numeric_limits<int>::max(); public: BellmanFord(int n) : n(n) { dist.assign(n, INF); } 

The Guild kept a ledger of distances from the starting city to all others.
At the start, all distances were infinite — for no one knew a way yet.

🚪 Carving the Roads

 void addEdge(int u, int v, int w) { edges.push_back({u, v, w}); } 

Every time a caravan returned with news of a road, it was carved into the scroll:
"From U to V, the toll is W."

🏁 The Departure

 void shortestPath(int src) { dist[src] = 0; 

The Guildmaster began in the chosen starting city src.
His distance to himself was 0 — no toll to stand where you already are.

🔄 The n-1 Journeys

 for (int i = 1; i <= n - 1; i++) { for (auto &e : edges) { if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) { dist[e.v] = dist[e.u] + e.w; } } } 

The caravans then began n-1 great journeys across the desert.

Why n-1?
Because in the worst case, the shortest path to a city might have to pass through every other city exactly once — and each journey could only improve distances by one road at a time.

On each journey:

• The caravans looked at every road in the scroll.
• If they could reach the starting point of a road (dist[e.u] != INF) and taking that road improved the distance to its end city (dist[e.u] + e.w < dist[e.v]), they updated the ledger.

Each improvement was like a rumor spreading: "There's a faster way, through here!"

🕳️ The Shadow Loops

 for (auto &e : edges) { if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) { cout << "Negative cycle detected\n"; return; } } 

When the n-1 journeys ended, the Guildmaster sent scouts for one final check.

If any road could still improve a distance, it meant they had found a shadow loop — a cursed cycle where merchants could ride forever, endlessly decreasing their toll cost, and break the economy.

The Guild marked such roads as forbidden and ended the expedition.

📖 The Ledger of Truth

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

If no cursed loop was found, the Guild unrolled the final ledger:

• If the number was finite, it was the shortest possible toll to reach that city.
• If INF, the city was unreachable — lost beyond the dunes.

🧪 The Day of the Caravan

int main() { BellmanFord g(5); g.addEdge(0, 1, -1); g.addEdge(0, 2, 4); g.addEdge(1, 2, 3); g.addEdge(1, 3, 2); g.addEdge(1, 4, 2); g.addEdge(3, 2, 5); g.addEdge(3, 1, 1); g.addEdge(4, 3, -3); g.shortestPath(0); } 

The expedition began in City 0.
Caravans rode for n-1 journeys, spreading rumors of faster paths, until all truth was known.

And in the end, the Guild could travel the desert without fear of deception — unless a shadow loop still lurked in the dunes.