Dijkstra's algorithm computes the shortest paths from a source node to all other nodes in a weighted graph with non‑negative edge weights. The procedure begins identical to SPFA: initialize all distances to infinity, set the source distance to zero, and mark the source as visited. Then, relax all edges from the source to update the disstances of its neighbors. The core loop repeats: among all univsited nodes, pick the one with the smallest current distance, mark it visited, and relax its outgoing edges.

The efficiency of the algorithm hinges on how we select the unvisited node with the smallest distance. Two common approaches exist:

• Linear scan: each iteration scans all n nodes to find the minimum. This yields O(n²) overall, comparable to a naive SPFA and not recommended for large graphs.
• Priority queue: whenever a node's distance is updated, push it into a min‑heap (a priority queue that returns the smallest element). Duplicate entries for the same node may appear, but a visited flag prevents reprocessing. This reduces the complexity to O(m log n), where m is the number of edges.

In C++, the standard priority_queue implements a max‑heap by default. To obtain a min‑heap we can either use a custom comparator or store negative distances. An elegant solution is to define a structure that holds the distance and node ID, and overload the < operator to invert the comparison. The code below demonstrates this technique.

#include <queue>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
int n, m, s;
vector<pair<int,int>> adj[100005]; // adjacency list: (neighbor, weight)
int dist[100005];
bool visited[100005];

struct MinHeapNode {
    int distance, id;
    bool operator<(const MinHeapNode &other) const {
        return distance > other.distance; // invert for min‑heap
    }
};

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back({v, w});   // directed edge
    }

    memset(dist, INF, sizeof(dist));
    dist[s] = 0;
    priority_queue<MinHeapNode> pq;
    pq.push({0, s});

    while (!pq.empty()) {
        int cur = pq.top().id;
        pq.pop();
        if (visited[cur]) continue;   // skip outdated entries
        visited[cur] = true;

        for (auto &edge : adj[cur]) {
            int next = edge.first;
            int w = edge.second;
            if (dist[next] > dist[cur] + w) {
                dist[next] = dist[cur] + w;
                pq.push({dist[next], next});   // push updated distance
            }
        }
    }

    for (int i = 1; i <= n; i++)
        printf("%d ", dist[i]);
    return 0;
}

Note that the graph is stored as a vector of vectors of pairs, simplifying edge traversal. The priority queue is declared with a custom MinHeapNode type that reverses the relational operator, effectively turning the default max‑heap into a min‑heap.