This content originally appeared on DEV Community and was authored by Harsh Mishra
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.
This content originally appeared on DEV Community and was authored by Harsh Mishra