DEV Community

Harsh Mishra
Harsh Mishra

Posted on

Bellman-Ford Algorithm C++: Story

#algorithms #programming #cpp

⚔️ 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;
};
Enter fullscreen mode Exit fullscreen mode

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);
    }
Enter fullscreen mode Exit fullscreen mode

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});
    }
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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;
                }
            }
        }
Enter fullscreen mode Exit fullscreen mode

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;
            }
        }
Enter fullscreen mode Exit fullscreen mode

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";
    }
};
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)