Dijkstra's Algorithm C++: Story

#cpp #programming #algorithms

🏹 The Beacon Riders of the Northern Realms — The Dijkstra Saga

"In the kingdom where roads shimmered with frost, the fastest rider was the one who chose his next step with care."
— Songs of the Winter Messenger

The Northern Realms were a land of villages connected by winding frozen roads, each road taking a certain amount of time to travel.
The High Council needed to send messengers from the capital to every other village, carrying news of an approaching winter storm.
But there was a rule: messengers must always choose the currently closest unexplored village to visit next, so no time would be wasted wandering far before checking nearer places.

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

class Dijkstra {
    int n;
    vector<vector<pair<int, int>>> adj;
    vector<int> dist;
    const int INF = numeric_limits<int>::max();
public:
    Dijkstra(int n) : n(n) {
        adj.resize(n);
        dist.assign(n, INF);
    }

The kingdom was drawn as n villages on a great frost-map.
Beside each village lay a ledger of roads: adj[u] kept track of every road from that village, written as (neighbor, time_cost).
dist[] was the parchment where the shortest known times to reach each village would be recorded.

    void addRoad(int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

Every road was carved into the map:
"From U to V, the ride takes W hours."
And because roads in the Northern Realms could be traveled in both directions, the same note was made for the reverse path.

    void shortestPaths(int src) {
        dist[src] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, src});

The messengers began at the capital (src).
The time to reach the capital itself was 0.
A magical beacon-fire, represented by a priority queue, was lit — its flames always showing the next closest village yet to be visited.

        while (!pq.empty()) {
            int d = pq.top().first;
            int u = pq.top().second;
            pq.pop();

At each step, the beacon’s flame called forth the nearest unexplored village.
The chosen village’s name was read, and the messenger rode there next.

            if (d > dist[u]) continue;

If a messenger arrived and found that a faster messenger had already reached this village before, they turned around without delay — no need to waste effort on a place already warned sooner.

            for (auto &edge : adj[u]) {
                int v = edge.first;
                int w = edge.second;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }

From each newly reached village, the messenger looked at every road leading outward.
If traveling through this village gave a shorter path to another village than previously known, the ledger was updated.
The beacon-fire was fed with this news, so those closer villages could be visited next.

And so, like ripples in ice, the shortest paths spread from the capital outward.

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

When the last flame of the beacon-fire faded, the ledger was unrolled before the High Council:

If a number was written, it was the fastest possible travel time from the capital to that village.
If INF, it meant the snow had blocked every road to that place — unreachable until the spring thaw.

int main() {
    Dijkstra realm(5);
    realm.addRoad(0, 1, 10);
    realm.addRoad(0, 4, 5);
    realm.addRoad(1, 2, 1);
    realm.addRoad(4, 1, 3);
    realm.addRoad(4, 2, 9);
    realm.addRoad(4, 3, 2);
    realm.addRoad(3, 2, 4);
    realm.addRoad(2, 3, 6);

    realm.shortestPaths(0);
}