Dijkstra's Algorithm

Every maps app, every network router and every game AI asks the same question: what is the cheapest way from here to everywhere? Once edges have lengths, counting edges (BFS) is no longer enough, and Dijkstra's algorithm is the answer.

★ Lecture: Graph_Dijkstra · Zaza Gamezardashvili▶ video intermediate⏱ 20 min read

←Builds on

6Breadth-First Search (BFS)Dijkstra is BFS whose wave moves by distance instead of by edge count.5Binary Heap & Priority QueueDijkstra keeps candidate distances in a min-heap.7The Greedy Idea & When It FailsDijkstra is greedy: it always fixes the closest unfinished vertex.

Leads to→

8Bellman–Ford & Negative EdgesBellman–Ford keeps Dijkstra's relaxation but repeats it over every edge, so negative weights are fine.8Minimum Spanning Tree: Kruskal & PrimPrim is Dijkstra with a different key: the cheapest edge into the tree, not the total distance.10Floyd–Warshall: DP on GraphsIt answers all pairs at once where Dijkstra answers one source.

1Learn 2Watch 3Play 4Check 5Practice

Learn

The idea, the mechanics and the cost.

01The problem: shortest paths from one vertex

Given a weighted graph, directed or undirected, where every edge weight is non-negative. Find the shortest distances from a chosen source vertex to all other vertices, and the paths themselves. The algorithm was found by the Dutch scientist Edsger Dijkstra in 1959.

Why not BFS? In the lecture graph, the route from 1 to 6 with the fewest edges (4 of them) costs 23, while a 6-edge route costs only 15. Path length is the sum of weights, not the number of edges.

The lecture lists related problems this one covers:

to one vertex v from everywhere: reverse every edge and run from v;
one pair u, v: run from u (nothing faster for a single pair is known);
all pairs: run from every vertex (Floyd–Warshall is more compact, not asymptotically faster).

The lecture graph: 9 vertices, 14 directed edges.

02Relaxation, and why parts of shortest paths are shortest

Keep a current best estimate d[v] for every vertex (∞ at first) and a parent p[v]. Relaxing the edge (a, b) with weight w means asking: is going through a better?

if d[a] + w < d[b]: d[b] = d[a] + w, p[b] = a

In the lecture's example the direct edge gives d[b] = 12; through c it is 5 + 4 = 9 < 12, so d[b] drops to 9 and b's parent becomes c. The routes through d (17) and through e, f (14) do not help.

Relaxation is enough thanks to a lemma: if P = ⟨v₁, …, vₖ⟩ is a shortest path, then every piece of it from vᵢ to vⱼ is also a shortest path. If a shorter detour existed, swapping it in would shorten P. So shortest paths are built out of shortest paths.

03The algorithm: closest unmarked vertex first

The lecture keeps three rows per vertex: distance, parent, color (0 not reached, 1 in the heap, 2 marked), plus a min-heap of (distance, vertex) pairs. Start: d[1] = 0, heap = (0, 1).

Each iteration: pop the smallest pair (d, u), mark u, then relax every edge leaving u, pushing (d[v], v) whenever d[v] improves. If a popped vertex is already marked, the pair is outdated: skip it.

This is a greedy algorithm, exactly the stage 7 idea: it commits to the closest unmarked vertex and never revisits it. After iteration 3 on the lecture graph, vertices 1, 7, 2 are marked; the heap holds (5,3) (8,3) (11,4) (12,4), and (8,3) will pop later as outdated, because 3 was improved from 8 to 5 through 7.

Numbers under the vertices are the current d[]; indigo edges are parent links.

04Recover the path: the shortest path tree

After 9 iterations the heap is empty and the table is final: distances 0 4 5 10 7 15 3 11 8 for vertices 1…9, parents Nil 1 7 9 3 8 1 9 5.

To recover the path to 6, follow parents back to the source: 6 ← 8 ← 9 ← 5 ← 3 ← 7 ← 1, total 15. The lecture's path(n) does it recursively: it first calls itself on parent[n], then prints n, so the path comes out in the right order.

The lemma on slide 18: the parent links form a tree rooted at the source, the shortest path tree. Every reachable vertex has exactly one parent (8 links for 9 vertices), so it has exactly one way back to 1. One run of Dijkstra answers "how far?" and "which way?" for every vertex at once.

05Why it works, what it costs, where it breaks

Correctness (by induction, as in the lecture): d[s] = 0 is right. Suppose all marked vertices are right and the algorithm now picks b. Any other route to b must leave the marked set through some unmarked x with d[x] ≥ d[b], and with non-negative weights the rest of that route can only add. So d[b] is final.

Cost: |V| iterations and |E| relaxation attempts in total. With a binary heap (priority_queue with greater<>, as in the lecture code) that is O((V + E) log V); with a Fibonacci heap O(E + V log V).

The trap: one negative edge breaks the induction. Below, A is marked with 2, but S→B→A costs 4 − 3 = 1. For negative weights you need Bellman–Ford, the next topic.

The lecture's C++C++

Slides 20, 21 and 22 joined into one program: the priority_queue with greater is a min heap of {distance, vertex} pairs, and parent[] lets path() print the route from vertex 1 to vertex n. Two things to know before running it. First, main() adds every edge in both directions, so the graph is treated as undirected: on the lecture’s directed example that gives d[6] = 13 instead of 15. For the directed slide graph, delete the second push_back. Second, the slide code has no check for outdated queue pairs. Read long long d = q.top().first; before the pop and add if (d > dis[u]) continue; right after it, so a vertex whose distance has already improved is not processed again.

#include<bits/stdc++.h>
#define inf 1000000000000
using namespace std;
vector < pair<int, int> >g[1000000];
long long dis[1000000], parent[1000000];
int n, m;
void path(int n) {
    if(n!=1) path(parent[n]);
    cout<<n<<" ";
}
void dijkstra(){
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    for(int i=0; i<=n; i++) dis[i]=inf;
    dis[1]=0;
    q.push({0, 1});
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        for(int i=0; i<g[u].size(); i++){
            int v=g[u][i].first;
            int w=g[u][i].second;
            if(dis[u]+w < dis[v]){
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
                parent[v]=u;
            }
        }
    }
}
int main(){
    int u, v, w;
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dijkstra();
    if(dis[n]==inf) cout<<"-1";
    else path(n);
}

Cost at a glance

Binary heap (priority_queue)O((V + E) log V)

Fibonacci heapO(E + V log V)

Path recovery to one vertexO(path length)

MemoryO(V + E)

Remember

Dijkstra always takes the closest unmarked vertex from a min-heap; once marked, its distance is final.
Relaxation d[v] = min(d[v], d[u] + w) plus parent pointers gives both distances and the shortest path tree.
It is a greedy algorithm that needs non-negative weights; with negative edges use Bellman–Ford.

Watch

The lecture as a narrated explainer video.

▶

Watch the lecture, animated

The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.

▶ Open the video page ▣ Open as presentation

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the min-heap: the first pair is always the next vertex to be marked. Compare each table with the lecture slides 7–15.

Interactive visualizerfocus here, then space ← →

Directed weighted graph (source: 1)

0: not reached1: in the heap2: markedshortest path tree

Min-heap (dist, vertex)

(0, 1)

State

v	1	2	3	4	5	6	7	8	9
dist	0	∞	∞	∞	∞	∞	∞	∞	∞
parent	nil	∞	∞	∞	∞	∞	∞	∞	∞
color	1	0	0	0	0	0	0	0	0

Initialize: dist[1] = 0, every other distance is ∞, every parent is Nil. Push (0, 1) into the min-heap.

Pseudocode

 1 dist[*]=∞; dist[s]=0; heap.push((0,s)) 2 while (!heap.empty()) { 3   (du, u) = heap.popMin() 4   if (u is marked) continue  // stale pair 5   mark u  // dist[u] is provably shortest 6   for (edge u→v with weight w) { 7     if (dist[u] + w >= dist[v]) skip 8     dist[v] = dist[u]+w; p[v] = u 9     heap.push((dist[v], v))10 } }  // relaxation / რელაქსაცია

1 / 1

Check

Three questions. Pick an answer to see why.

Lecture graph: after vertex 1 is marked, d[3] = 8. Then vertex 7 (d = 3) is marked, and 7→3 has weight 2. What is d[3] now?

The heap pops (8, 3), but vertex 3 is already marked with distance 5. What does the algorithm do?

Why can a negative edge make Dijkstra wrong?

Practice

Real problems to lock it in, easiest first.

LeetCodeNetwork Delay Time intermediate↗CSESShortest Routes I intermediate↗LeetCodePath With Minimum Effort intermediate↗CSESFlight Discount advanced↗