⚔️ 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.
SOCIAL SHARE CARD GENERATOR