This content originally appeared on DEV Community and was authored by Harsh Mishra
🏹 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.
This content originally appeared on DEV Community and was authored by Harsh Mishra
Harsh Mishra | Sciencx (2025-08-16T20:58:49+00:00) Dijkstra’s Algorithm C++: Story. Retrieved from https://www.scien.cx/2025/08/16/dijkstras-algorithm-c-story/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.