Dijkstra’s Algorithm

July 2026 · 25 min read

Given a weighted graph with non-negative edge weights, how do you find the shortest path from a single source to every other vertex? Dijkstra’s algorithm answers this with an elegant greedy strategy: always process the closest unvisited vertex. In this post we cover the full algorithm with a priority-queue implementation, a detailed visual walkthrough, an interactive animation, why negative weights break it, clean C++ code, and competitive-programming patterns you should know.

Why Dijkstra’s Algorithm?

When edges carry non-negative weights, BFS no longer gives shortest paths. We need an algorithm that accounts for edge costs. Dijkstra’s algorithm solves the single-source shortest path problem by greedily extracting the nearest unvisited vertex and relaxing its neighbors.

Published by Edsger Dijkstra in 1959, it remains one of the most important graph algorithms. Applications include:

• GPS navigation — finding the fastest route between two locations
• Network routing — OSPF protocol uses Dijkstra to compute routing tables
• Game AI — pathfinding on weighted terrain maps
• Competitive programming — countless shortest-path problems

The Algorithm

Dijkstra maintains a distance array dist[] initialized to ∞ for all vertices except the source (which is 0). A priority queue (min-heap) always extracts the vertex with the smallest tentative distance.

dist[source] = 0
pq.push({0, source})

while pq is not empty:
    (d, u) = pq.extractMin()
    if d > dist[u]: continue   // stale entry
    for each edge (u, v, w):
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            pq.push({dist[v], v})

Key insight: When we extract vertex u from the priority queue, dist[u] is finalized. This works because all edge weights are ≥ 0, so no future path through unvisited vertices can improve it.

Why Non-Negative Weights?

If an edge has negative weight, a vertex we already “finalized” might later find a shorter path through that negative edge. Dijkstra’s greedy assumption breaks.

Step-by-Step Walkthrough

Let’s trace Dijkstra on a 7-node weighted graph starting from node 0.

Shortest paths: 0→2 (cost 1), 0→2→1 (cost 3), 0→2→1→3 (cost 4), 0→2→1→3→5 (cost 5), 0→2→4 (cost 6), 0→2→4→6 (cost 8).

Why Negative Weights Break Dijkstra

Dijkstra’s greedy invariant says: “once a node is extracted from the priority queue, its distance is final.” Negative edges violate this because a longer initial path can become shorter after traversing a negative edge.

Counterexample

Consider this 4-node graph with one negative edge (dashed red):

Dijkstra’s execution:

1. Extract S (dist=0). Relax: dist[A]=1, dist[B]=5.
2. Extract A (dist=1). Mark A as finalized. Relax: dist[C]=1+2=3.
3. Extract C (dist=3). Mark C as finalized.
4. Extract B (dist=5). Relax B→C: dist[C] would become 5+(−4)=1, but C is already finalized with dist=3. Skipped!

Dijkstra’s answer: dist[C]=3 (via S→A→C). Correct answer: dist[C]=1 (via S→B→C = 5−4 = 1). The greedy assumption “extracted = optimal” fails because the cheaper path goes through a longer initial segment followed by a negative edge.

Interactive Animation

Step through Dijkstra’s algorithm on the 7-node weighted graph. Watch the priority queue and distance array update in real time.

Priority Queue Variants & Optimizations

Binary Heap (Standard)

The standard implementation uses a binary min-heap (C++ priority_queue, Python heapq). Insert and extract-min are both O(log n). This gives O((V+E) log V) overall — the go-to for competitive programming.

Fibonacci Heap (Theoretical)

A Fibonacci heap supports decrease-key in O(1) amortized, reducing Dijkstra’s complexity to O(V log V + E). In practice, the constant factors are large, so binary heaps are faster for most graph sizes. Fibonacci heaps matter mainly for theoretical results and very dense graphs.

Lazy Deletion vs. Decrease-Key

Instead of implementing decrease-key (which binary heaps don’t natively support), we use lazy deletion: push a new (dist, v) pair and skip stale entries on extraction. This is simpler and performs well in practice, though the PQ can hold O(E) entries instead of O(V).

Dial’s Algorithm & 0-1 BFS

When all edge weights are small integers in [0, C], Dial’s algorithm uses an array of C+1 buckets instead of a heap, giving O(V·C + E). The special case where C=1 (all edges weight 0 or 1) leads to 0-1 BFS using a deque — push weight-0 edges to the front, weight-1 edges to the back. This runs in O(V+E).

C++ Implementation

Standard Dijkstra with Priority Queue

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

vector<long long> dijkstra(int src, const vector<vector<pair<int,int>>>& adj) {
    int n = adj.size();
    vector<long long> dist(n, LLONG_MAX);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>,
                   greater<pair<long long,int>>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue; // stale entry

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

With Path Reconstruction

pair<vector<long long>, vector<int>> dijkstra_path(int src,
    const vector<vector<pair<int,int>>>& adj) {
    int n = adj.size();
    vector<long long> dist(n, LLONG_MAX);
    vector<int> parent(n, -1);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>,
                   greater<>> pq;

    dist[src] = 0;
    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;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
    return {dist, parent};
}

// Reconstruct path from src to dst
vector<int> getPath(int dst, const vector<int>& parent) {
    vector<int> path;
    for (int v = dst; v != -1; v = parent[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    return path;
}

Complexity Analysis

Time Complexity

Why O((V+E) log V)?

Each vertex is extracted from the PQ at most once (stale entries are skipped in O(1)). Each edge is relaxed at most once, and each relaxation involves one PQ insertion costing O(log V). Total: V extractions × O(log V) + E insertions × O(log V) = O((V+E) log V).

Space Complexity

O(V + E) for the adjacency list and distance array. The priority queue can hold up to O(E) entries with lazy deletion (each edge relaxation may push one entry). In practice, this is rarely a bottleneck.

For most competitive programming problems: V, E ≤ 10⁵–10⁶, so the binary heap version is fast enough.

Competitive Programming Patterns

Dijkstra appears in many disguises in competitive programming. Here are the most common patterns:

1. Shortest Path on Grid

Many CP problems give a 2D grid where each cell has a cost. Model it as a graph: each cell is a node, edges go to 4 (or 8) neighbors with the neighbor’s cost as edge weight. Run Dijkstra from top-left to bottom-right. If costs are 0 or 1, prefer 0-1 BFS with a deque for O(V+E) performance.

2. Multi-Source Dijkstra

Need shortest distance from any of several source nodes? Push all sources into the PQ with dist=0 at the start. The algorithm runs identically — it’s equivalent to adding a virtual super-source with zero-weight edges to all real sources. Used in problems like “distance to nearest hospital” or “escape fire.”

3. Modified Edge Weights

Some problems require transforming edge weights. Example: “maximize the minimum edge on a path” — negate weights and use Dijkstra, or modify the relaxation condition. Another example: “path with maximum probability” — use a max-heap and multiply probabilities instead of adding costs.

4. Dijkstra on States (State-Space Expansion)

Add extra dimensions: dist[node][state]. Example: “shortest path using at most K toll roads” — state = (node, tolls_used). The graph expands from V nodes to V×K nodes. Example: “you can teleport once” — state = (node, teleported?). This is an extremely powerful technique for handling constraints.

5. Bidirectional Dijkstra

For single-pair shortest paths, run Dijkstra simultaneously from source and target. Stop when the two search frontiers meet. Approximately 2× faster in practice. Real-world navigation systems (e.g., Contraction Hierarchies) build on this idea for even faster queries.

Practice Problems

Test your understanding with these problems, ordered roughly by difficulty:

Summary

Key takeaways from this post:

1. Dijkstra’s algorithm finds shortest paths from a single source in graphs with non-negative edge weights using a greedy, priority-queue-based approach.
2. The core operation is relaxation: for each edge u→v(w), check if dist[u]+w improves dist[v].
3. Lazy deletion (skip stale PQ entries) is simpler and faster in practice than decrease-key.
4. Negative weights break Dijkstra because the greedy invariant (“extracted = finalized”) no longer holds. Use Bellman-Ford instead.
5. Time complexity is O((V+E) log V) with a binary heap — the standard for competitive programming.
6. For CP, know these patterns: grid shortest paths, multi-source Dijkstra, state-space expansion, and 0-1 BFS for weights in {0, 1}.