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:

4 5
1 2 1
1 3 4
2 3 2
2 4 5
3 4 1

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

1. Push (0, start) into the priority queue.
2. 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.

1. 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

Easy

• CSES – Shortest Routes I https://cses.fi/problemset/task/1671/

• Codeforces 20C – Dijkstra? https://mirror.codeforces.com/problemset/problem/20/C

Medium

• Codeforces 715B – Complete The Graph https://mirror.codeforces.com/problemset/problem/715/B

• AtCoder ABC362E – Count Arithmetic Subsequences https://atcoder.jp/contests/abc362/tasks/abc362_e

Hard

• Codeforces 464E – The Classic Problem https://mirror.codeforces.com/problemset/problem/464/E