Bellman-Ford Algorithm C++: Story

[MyrinNew]

⚔️ 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
#include
#include
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;
vectorEdge> edges;
vectorint> dist;
const int INF = numeric_limitsint>::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 ),
  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.




More...