Dijkstra's Algorithm

Shortest path in non-negative weighted graphs using priority queue relaxation in O((V+E) log V).

[Graph]|

Jul 9, 2026

|explanatory_notes.md|

#dijkstra#shortest-path#priority-queue#graph

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pli = pair<ll, int>;

const ll INF = 1e18;

vector<vector<pair<int, ll>>> adj;
vector<ll> dist;

void dijkstra(int src, int n) {
    dist.assign(n + 1, INF);
    dist[src] = 0;
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto &[v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

26 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Dijkstra's Algorithm

Single-source shortest path for graphs with non-negative edge weights.

How It Works

Initialize all distances to

\infty

, source to

0

Use a min-priority queue. Extract the node with smallest distance

Skip if already processed (distance check)

Relax all neighbors: if

d[u] + w < d[v]

, update

d[v]

and push to queue

When to Use

Single-source shortest path with non-negative weights

Grid pathfinding, state-space search with weighted transitions

Fails with negative weights — use Bellman-Ford instead

Complexity

Time —

O((V + E) \log V)

with binary heap

Space —

O(V + E)