Dijkstra's Algorithm C++: Story

🏹 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);

}

The messengers rode, flames guiding them village by village, until the whole kingdom had been warned — in the fastest way possible.