Dijkstra's Algorithm (Priority Queue Version)

In this blog, we discuss an implementation of Dijkstra's Algorithm to compute the shortest paths from a single source in a directed weighted graph with non-negative weights.

Problem Setting

We are given:

n nodes (numbered from 1 to n)
m directed edges
Each edge has weight w ≥ 0

Goal: Find the shortest distance from node 1 to every other node.

Example

Input:

Output:

0 1 3 4

Explanation:

Node 1 → Node 1: distance = 0
Node 1 → Node 2: distance = 1 (direct edge)
Node 1 → Node 3: distance = 3 (path: 1 → 2 → 3)
Node 1 → Node 4: distance = 4 (path: 1 → 2 → 3 → 4)

When to Use Dijkstra

Use Dijkstra when:

The graph is weighted
All weights are non-negative
You need shortest paths from a single source

Do NOT use Dijkstra when:

Negative edge weights → use Bellman-Ford or SPFA
All-pairs shortest paths → use Floyd-Warshall
Unweighted graph → use BFS (O(n + m))
Tree structure → use DFS/BFS

Core Idea

We use a min-priority queue to always process the node with the smallest current distance.

Key observation:

The first time we pop a node from the priority queue, we have already found its shortest distance.

So once a node is marked as visited (finalized), we never process it again.

Data Structures

adj[u] — adjacency list storing (neighbor, weight)
dis[i] — shortest distance to node i
vis[i] — whether the node has been finalized
priority_queue — min-heap ordered by distance

Important: In C++, priority_queue is a max-heap by default. We use greater<> to turn it into a min-heap.

Algorithm Steps

Push (0, start) into the priority queue.
While the queue is not empty:

Extract the node with the smallest cost.
If already visited, skip it.
Mark it as visited.
Fix its distance.
Push all unvisited neighbors with updated cost.

Continue until the queue becomes empty.

Time Complexity: O((n + m) log n)

Implementation

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 2e5 + 5;

int n, m;
ll dis[N];
vector<pair<int,ll>> adj[N];
bool vis[N];

void dijkstra(int start)
{
    priority_queue<
        pair<ll,int>,
        vector<pair<ll,int>>,
        greater<pair<ll,int>>
    > pq;

    pq.push({0, start});

    while(!pq.empty())
    {
        auto p = pq.top();
        pq.pop();

        ll cost = p.first;
        int node = p.second;

        if(vis[node]) continue;

        vis[node] = true;
        dis[node] = cost;

        for(auto [next, weight] : adj[node])
        {
            if(!vis[next])
            {
                pq.push({cost + weight, next});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    dijkstra(1);

    for(int i = 1; i <= n; i++)
    {
        if(vis[i])
            cout << dis[i] << " ";
        else
            cout << -1 << " ";
    }
}

---

Practice Problems

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Problem Setting

Example

When to Use Dijkstra

Core Idea

Data Structures

Algorithm Steps

Implementation

Practice Problems

Easy

Medium

Hard

History