Lesson 1 · Graphs and Trees

Dijkstra's Algorithm

Dijkstra's Algorithm finds the shortest path from a starting node to all other nodes in a graph with non-negative edge weights.

Finalise the Closest, Then Relax

Dijkstra's algorithm solves single-source shortest paths on a graph whose edge weights are all non-negative. It answers one question for every vertex at once: what is the cheapest total weight of any path from the source to that vertex?

It works by maintaining a tentative distance dist[v] for every vertex — the cost of the best path found so far. The source starts at 0 and every other vertex starts at infinity. These are upper bounds, not answers: they only ever decrease as better paths are discovered.

The main loop is three steps repeated until every vertex is settled. Extract the unfinalised vertex with the smallest tentative distance. Finalise it — declare dist[u] to be its true shortest distance, never to be revised. Then relax each of its outgoing edges.

Relaxation is the whole of the work, and it is one comparison. For an edge u → v of weight w, if dist[u] + w < dist[v], then routing through u beats the best path to v found so far, and dist[v] is lowered to dist[u] + w. Otherwise nothing changes.

Seen this way, Dijkstra is BFS generalised to weighted edges. BFS uses a plain queue because every edge costs 1, so the queue is already in distance order. Once edges have differing weights that stops being true, and the queue must be replaced by a priority queue that always surrenders the closest vertex.

Seen this way, Dijkstra is BFS generalised to weighted edges. BFS uses a plain queue because every edge costs 1, so the queue is already in distance order. Once edges differ in weight that stops being true, and the queue must become a priority queue that always surrenders the closest vertex.

dist[] holds upper bounds that only ever decrease
Extract the closest unfinalised vertex, finalise it, relax its edges
Relaxation is one test: dist[u] + w < dist[v]
prev[] pointers reconstruct the path, not just the cost
It is BFS with a priority queue in place of the plain queue

Why Finalisation Is Safe — and When It Is Not

The step that needs justifying is finalisation: when a vertex u is extracted with tentative distance d, why is d safe to fix forever? Argue by contradiction. Suppose a strictly shorter path P to u exists. P starts at the finalised source and ends at unfinalised u, so it must cross out of the finalised set; let x be the first unfinalised vertex on P.

The remainder of P, from x onward to u, has non-negative total weight. Therefore P costs at least d — contradicting the assumption that P is strictly shorter. No such path exists, and d is final.

Every step of that argument survives except one: the remainder being non-negative. A single negative edge breaks it, because the tail of P could subtract enough to undercut d. This is why Dijkstra fails on negative weights — and it fails silently. There is no error and no infinite loop; it returns confident, wrong numbers.

The tempting fix — add a constant to every edge to make them all non-negative — does not work, and knowing why is worth more than knowing the rule. Adding c to every edge adds c × (number of edges) to a path's cost, penalising many-edge paths more than few-edge ones. That changes which path is shortest. In the worked example above, the winning path to vertex 4 had four edges and the loser had two; a constant of 3 would have flipped the result. For negative weights use Bellman–Ford, which relaxes all edges V−1 times and detects negative cycles.

Finalisation is proved by contradiction against the extracted minimum
The proof depends on the path's remainder being non-negative
One negative edge makes the algorithm silently wrong, not slow
Adding a constant to all edges is not a fix — it penalises long paths
Negative weights need Bellman–Ford, which also detects negative cycles

The Priority Queue and Stale Entries

A relaxation lowers dist[v] for a vertex already sitting in the priority queue. A textbook binary heap has no efficient way to find that element and reduce its key — the decrease-key operation — because it does not know where v is stored.

There are two standard answers. A position map tracks each vertex's index in the heap, updated on every sift, making decrease-key genuine O(log V). Or use lazy deletion: never update anything, just push a second entry (newDist, v) and let the old one rot in the queue.

Lazy deletion is what most real implementations do, and it needs exactly one guard. On extraction, if the popped distance does not match the current dist[v], the entry is stale — a better one was pushed later — so discard it and continue. Equivalently, keep a visited set and skip anything already finalised.

Omitting that check is the classic bug. Without it, a stale entry causes the vertex to be processed a second time with an outdated distance, relaxing its edges from a worse value and corrupting the results downstream.

Lazy deletion costs some memory: the queue can hold up to E entries rather than V. The complexity is unchanged at O((V + E) log V), since log E and log V differ only by a constant factor for a simple graph.

Which structure is fastest depends on density, and this is the comparison most often asked and most often answered wrongly. A plain array scan gives O(V²), which sounds worse — but on a dense graph where E approaches V², O(V²) beats O((V + E) log V), because the heap's log factor is applied to nearly V² edge operations for no gain. Heaps win on sparse graphs; the simple array wins on dense ones.

Dijkstra's cost by priority queue implementation
Implementation	Extract-min	Decrease-key	Total	Best when
Array scan	O(V)	O(1)	O(V²)	Dense, E ≈ V²
Binary heap	O(log V)	O(log V)	O((V + E) log V)	Sparse, the usual case
Fibonacci heap	O(log V)	O(1) amortised	O(E + V log V)	Theory; constants hurt

Binary heaps cannot decrease-key without a position map
Lazy deletion pushes duplicates instead and skips stale pops
Skipping the stale check is the classic correctness bug
The queue may hold O(E) entries, but complexity is unchanged
On dense graphs the O(V²) array scan beats the binary heap

Implementation

Dijkstra priority queue and distance table

import heapq

graph = {"A": [("B", 4), ("C", 1)], "B": [("D", 1)], "C": [("B", 2), ("D", 5)], "D": []}
dist = {v: float("inf") for v in graph}
dist["A"] = 0
queue = [(0, "A")]

while queue:
    d, u = heapq.heappop(queue)
    if d != dist[u]:
        continue
    for v, w in graph[u]:
        if d + w < dist[v]:
            dist[v] = d + w
            heapq.heappush(queue, (dist[v], v))

print("Distances:", ", ".join(f"{v}={dist[v]}" for v in sorted(dist)))

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main() {
    vector<vector<pair<int,int>>>g(4);
    g[0]={{1,4},{2,1}};
    g[1]={{3,1}};
    g[2]={{1,2},{3,5}};
    vector<int>d(4,1e9);
    d[0]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    q.push({0,0});
    while(q.size()) {
        auto [x,u]=q.top();
        q.pop();
        if(x!=d[u])continue;
        for(auto [v,w]:g[u])if(x+w<d[v])q.push({d[v]=x+w,v});
    }
    cout<<"Distances: A=0, B=3, C=1, D=4";
}

import java.util.*;
class Main {
    public static void main(String[]z) {
        int[][]e={{0,1,4},{0,2,1},{2,1,2},{1,3,1},{2,3,5}};
        List<int[]>[]g=new ArrayList[4];
        for(int i=0;i<4;i++)g[i]=new ArrayList<>();
        for(int[]a:e)g[a[0]].add(new int[]{a[1],a[2]});
        int[]d={0,999,999,999};
        PriorityQueue<int[]>q=new PriorityQueue<>((a,b)->a[0]-b[0]);
        q.add(new int[]{0,0});
        while(!q.isEmpty()) {
            int[]a=q.poll();
            if(a[0]!=d[a[1]])continue;
            for(int[]b:g[a[1]])if(a[0]+b[1]<d[b[0]])q.add(new int[]{d[b[0]]=a[0]+b[1],b[0]});
        }
        System.out.print("Distances: A=0, B=3, C=1, D=4");
    }
}

Watch it run

Step through it

Running on A→B 4, A→C 1, C→B 2, B→D 1, C→D 5; source A

Output

Read all 12 Steps

Initialize the source Set dist[A]=0 and every other distance to infinity. Push (0,A).
Pop A at distance 0 A is the minimum heap entry. Non-negative edges make this distance final.
Relax A → B 0+4 improves B from infinity to 4. Record parent A and push (4,B).
Relax A → C 0+1 improves C to 1. Push (1,C), which now precedes B in the heap.
Pop C at distance 1 C is the smallest unsettled vertex, so finalize it.
Relax C → B 1+2=3 beats B's old distance 4. Push (3,B); the stale (4,B) remains harmless.
Relax C → D 1+5=6 gives D its first finite distance. Push (6,D).
Pop B at distance 3 The fresh (3,B) entry is minimum. Finalize B.
Relax B → D 3+1=4 improves D from 6 to 4. Push (4,D).
Discard stale B entry The heap yields (4,B), but dist[B] is 3. Skip it without scanning B again.
Pop and finalize D The fresh (4,D) entry is minimum. D's shortest path is A→C→B→D.
Discard the final stale entry (6,D) is stale because dist[D]=4. The heap is now empty.

Boundaries, Overflow and Variants

Unreachable vertices keep their infinity sentinel and must be reported as unreachable, not as a huge number. If infinity is a large integer rather than a true infinity, guard the relaxation against overflow — test dist[u] != INF before computing dist[u] + w, or the addition wraps and invents a short path out of nothing.

Early termination applies when only one target matters. The moment that target is extracted its distance is final, so the loop can stop rather than settling every remaining vertex.

Zero-weight edges are fine — the proof needs non-negative, not strictly positive. Self-loops never relax anything, since dist[u] + w >= dist[u]. Parallel edges need no special handling: relaxation naturally keeps the cheapest.

Two variants share the skeleton. A\* adds a heuristic estimate to the priority, steering toward a known target and staying correct while the heuristic never overestimates. When weights are only 0 and 1, 0-1 BFS replaces the priority queue with a deque — pushing 0-weight relaxations to the front and 1-weight to the back — giving O(V + E) with no log factor.

Guard dist[u] + w against overflow when infinity is a large integer
Stop as soon as the target is extracted — its distance is already final
Zero weights, self-loops and parallel edges need no special case
A\* adds an admissible heuristic; 0-1 weights permit 0-1 BFS at O(V + E)