Dijkstra's Algorithm C++: Story

[MyrinNew]

🏹 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
#include
#include
#include
using namespace std;

class Dijkstra {
int n;
vectorvectorpairint, int>>> adj;
vectorint> dist;
const int INF = numeric_limitsint>::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_queuepairint, int>, vectorpairint, int>>, greaterpairint, 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.




More...