35.03Intermediate / Advanced5 topics20 min4 interactive animations

Dijkstra's algorithm

Dijkstra's algorithm settles vertices in order of distance, each time taking the closest unsettled one; with non-negative weights this is correct, and a priority queue makes it O((n + m) log n).

Learning goals

Explain why non-negative weights make the greedy choice safe
Implement Dijkstra with a priority queue and lazy deletion
Count how many outdated entries the queue produces
Describe an indexed heap with decrease-key
Reconstruct a path from parent links

Prerequisites

Shortest path frameworkPriority queues

Road routing, network latency and game movement all need the cheapest path with positive costs. Dijkstra's greedy idea, always finish the closest unfinished vertex next, solves them in near-linear time.

35.03.1

Nonnegative weights

Dijkstra keeps a set of settled vertices whose distances are final. At each step it settles the unsettled vertex u with the smallest estimate. Why is it final? Any other route to u must leave the settled set through some other unsettled vertex x, whose estimate is at least as large, and then add non-negative weights, so it cannot be cheaper than the estimate of u.

The argument needs every weight to be at least 0. Zero weights are fine. This simple version scans for the minimum each time and costs O(n²), which is best for dense graphs; the heap versions below win on sparse ones.

Java

1static long[] dijkstraQuadratic(int n, int[][] edges, int s) {    // O(n^2); weights >= 0
2    long INF = Long.MAX_VALUE / 2;
3    long[][] w = new long[n][n];
4    for (long[] r : w) Arrays.fill(r, INF);
5    for (int[] e : edges) w[e[0]][e[1]] = Math.min(w[e[0]][e[1]], e[2]);   // lightest parallel edge
6    long[] dist = new long[n];
7    Arrays.fill(dist, INF);
8    dist[s] = 0;
9    boolean[] done = new boolean[n];
10    for (int step = 0; step < n; step++) {
11        int u = -1;
12        for (int v = 0; v < n; v++) if (!done[v] && dist[v] < INF && (u == -1 || dist[v] < dist[u])) u = v;
13        if (u == -1) break;                                      // the rest is unreachable
14        done[u] = true;
15        for (int v = 0; v < n; v++)
16            if (w[u][v] < INF && dist[u] + w[u][v] < dist[v]) dist[v] = dist[u] + w[u][v];
17    }
18    return dist;
19}

Dijkstra's shortest paths, and why negative edges break it

Interactive · edit the input

dist[] from vertex 0

0v0

∞v1

∞v2

∞v3

Setup

Distances start at ∞ except the source. Each step settles the closest unsettled vertex and relaxes its outgoing edges. Its distance is declared final, which is only justified when no edge is negative.

Step 1 / 11

Java

1static int[] dijkstra(int n, List<int[]>[] adj, int src) {  // adj[u] = list of {v, weight}
2    int[] dist = new int[n]; Arrays.fill(dist, INF); dist[src] = 0;
3    boolean[] done = new boolean[n];
4    for (int step = 0; step < n; step++) {
5        int u = -1;
6        for (int v = 0; v < n; v++) if (!done[v] && dist[v] < INF && (u == -1 || dist[v] < dist[u])) u = v;   // closest unsettled vertex
7        if (u == -1) break;
8        done[u] = true;                                       // final: valid only when no edge is negative
9        for (int[] e : adj[u]) if (!done[e[0]] && dist[u] + e[1] < dist[e[0]]) dist[e[0]] = dist[u] + e[1];   // relax
10    }
11    return dist;
12}

Live state

vertices

negative

false

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L2	vertices=4 negative=false	Distances start at ∞ except the source. Each step settles the closest unsettled vertex and relaxes its outgoing edges. Its distance is declared final, which is only justified when no edge is negative.
2	L8	settled=0 dist=0	Settle vertex 0 with distance 0: from now on it will not be updated.
3	L9	edge=0>1:4 new dist=4	Relax 0>1: 0 + 4 = 4 beats the old distance.
4	L9	edge=0>2:1 new dist=1	Relax 0>2: 0 + 1 = 1 beats the old distance.
5	L8	settled=2 dist=1	Settle vertex 2 with distance 1: from now on it will not be updated.
6	L9	edge=2>1:2 new dist=3	Relax 2>1: 1 + 2 = 3 beats the old distance.
7	L9	edge=2>3:5 new dist=6	Relax 2>3: 1 + 5 = 6 beats the old distance.
8	L8	settled=1 dist=3	Settle vertex 1 with distance 3: from now on it will not be updated.
9	L9	edge=1>3:1 new dist=4	Relax 1>3: 3 + 1 = 4 beats the old distance.
10	L8	settled=3 dist=4	Settle vertex 3 with distance 4: from now on it will not be updated.
11	L11	return=[0, 3, 1, 4] reference=[0, 3, 1, 4]	Distances [0, 3, 1, 4] match the Bellman-Ford reference.

35.03.2

Priority queue

A **priority queue** hands back the unsettled vertex with the smallest estimate in O(log n). Each time an edge improves an estimate, push the new {distance, vertex} pair. The total number of pushes is at most the number of edges, so the running time is O(m log m), which is O(m log n).

Java's PriorityQueue has no decrease-key operation, so the usual approach pushes a fresh entry and ignores the old one when it comes out, described next. The animation shows the queue as a sorted list of pairs.

Java

1static long[] dijkstraHeap(int n, List<int[]>[] adj, int s) {     // adj[u] = {v, w}, all w >= 0
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n];
4    Arrays.fill(dist, INF);
5    dist[s] = 0;
6    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));   // {distance, vertex}
7    pq.add(new long[]{0, s});
8    while (!pq.isEmpty()) {
9        long[] top = pq.poll();
10        int u = (int) top[1];
11        if (top[0] > dist[u]) continue;                           // outdated entry
12        for (int[] e : adj[u])
13            if (dist[u] + e[1] < dist[e[0]]) {
14                dist[e[0]] = dist[u] + e[1];
15                pq.add(new long[]{dist[e[0]], e[0]});
16            }
17    }
18    return dist;
19}

Dijkstra with a priority queue: lazy deletion and path reconstruction

Interactive · edit the input

undirected graph · 6 vertices · 9 edges

d=0

Being settledHas a queue entrySettledTree edge / on the pathOutdated entry skipped

queue {dist, vertex}, smallest first

0,0

dist[v]

∞1

∞2

∞3

∞4

∞5

Setup

Start with {0, 0} in the priority queue. The queue always gives the unsettled vertex with the smallest known distance; with non-negative weights nothing found later can beat it.

Step 1 / 28

Java

1long[] dijkstra(int n, List<int[]>[] adj, int s, int[] parent) {   // adj[u] = {v, w}, all w >= 0
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
4    Arrays.fill(parent, -1);
5    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));   // {distance, vertex}
6    pq.add(new long[]{0, s});
7    while (!pq.isEmpty()) {
8        long[] top = pq.poll(); int u = (int) top[1];
9        if (top[0] > dist[u]) continue;           // outdated entry: u was already improved
10        for (int[] e : adj[u]) {
11            if (dist[u] + e[1] >= dist[e[0]]) continue;
12            dist[e[0]] = dist[u] + e[1]; parent[e[0]] = u;
13            pq.add(new long[]{dist[e[0]], e[0]});   // lazy: the old entry stays in the queue
14        }
15    }
16    return dist;
17}
18List<Integer> pathTo(int[] parent, int t) {       // follow parents back from t
19    LinkedList<Integer> p = new LinkedList<>();
20    for (int v = t; v != -1; v = parent[v]) p.addFirst(v);
21    return p;
22}

Live state

1 entries pushed0 outdated entries skipped

source

No condition evaluated on this step

Execution trace (dry run table)Show 28 steps

Step	Line	State	What happens
1	L6	source=0	Start with {0, 0} in the priority queue. The queue always gives the unsettled vertex with the smallest known distance; with non-negative weights nothing found later can beat it.
2	L8	u=0 dist[u]=0	Pop {0, 0}: the distance to 0 is final (0). Relax its edges.
3	L12	u=0 v=1 dist[v]=7	0 → 1: 0 + 7 = 7. dist[1] = 7, parent[1] = 0, and a new entry {7, 1} is pushed.
4	L12	u=0 v=2 dist[v]=9	0 → 2: 0 + 9 = 9. dist[2] = 9, parent[2] = 0, and a new entry {9, 2} is pushed.
5	L12	u=0 v=5 dist[v]=14	0 → 5: 0 + 14 = 14. dist[5] = 14, parent[5] = 0, and a new entry {14, 5} is pushed.
6	L8	u=1 dist[u]=7	Pop {7, 1}: the distance to 1 is final (7). Relax its edges.
7	L10	u=1 v=0 candidate=14	1 → 0: 7 + 7 = 14 does not beat 0.
8	L10	u=1 v=2 candidate=17	1 → 2: 7 + 10 = 17 does not beat 9.
9	L12	u=1 v=3 dist[v]=22	1 → 3: 7 + 15 = 22. dist[3] = 22, parent[3] = 1, and a new entry {22, 3} is pushed.
10	L8	u=2 dist[u]=9	Pop {9, 2}: the distance to 2 is final (9). Relax its edges.
11	L10	u=2 v=0 candidate=18	2 → 0: 9 + 9 = 18 does not beat 0.
12	L10	u=2 v=1 candidate=19	2 → 1: 9 + 10 = 19 does not beat 7.
13	L12	u=2 v=3 dist[v]=20	2 → 3: 9 + 11 = 20. dist[3] = 20, parent[3] = 2, and a new entry {20, 3} is pushed; the older, larger entry for 3 stays in the queue.
14	L12	u=2 v=5 dist[v]=11	2 → 5: 9 + 2 = 11. dist[5] = 11, parent[5] = 2, and a new entry {11, 5} is pushed; the older, larger entry for 5 stays in the queue.
15	L8	u=5 dist[u]=11	Pop {11, 5}: the distance to 5 is final (11). Relax its edges.
16	L10	u=5 v=0 candidate=25	5 → 0: 11 + 14 = 25 does not beat 0.
17	L10	u=5 v=2 candidate=13	5 → 2: 11 + 2 = 13 does not beat 9.
18	L12	u=5 v=4 dist[v]=20	5 → 4: 11 + 9 = 20. dist[4] = 20, parent[4] = 5, and a new entry {20, 4} is pushed.
19	L9	entry=14,5 dist[v]=11	Pop {14, 5}, but dist[5] is already 11: this entry is outdated (a shorter route was found after it was pushed). Skip it. Skipping instead of deleting is called lazy deletion.
20	L8	u=3 dist[u]=20	Pop {20, 3}: the distance to 3 is final (20). Relax its edges.
21	L10	u=3 v=1 candidate=35	3 → 1: 20 + 15 = 35 does not beat 7.
22	L10	u=3 v=2 candidate=31	3 → 2: 20 + 11 = 31 does not beat 9.
23	L10	u=3 v=4 candidate=26	3 → 4: 20 + 6 = 26 does not beat 20.
24	L8	u=4 dist[u]=20	Pop {20, 4}: the distance to 4 is final (20). Relax its edges.
25	L10	u=4 v=3 candidate=26	4 → 3: 20 + 6 = 26 does not beat 20.
26	L10	u=4 v=5 candidate=29	4 → 5: 20 + 9 = 29 does not beat 11.
27	L9	entry=22,3 dist[v]=20	Pop {22, 3}, but dist[3] is already 20: this entry is outdated (a shorter route was found after it was pushed). Skip it. Skipping instead of deleting is called lazy deletion.
28	L15	return=[0, 7, 9, 20, 20, 11] pushed=8 skipped=2	Distances: [0, 7, 9, 20, 20, 11] (∞ = unreachable). 8 entries pushed, 2 skipped as outdated; each arrow pushes at most one entry (an undirected edge is two arrows), so the cost is O(m log m). Following parents back from 4 gives the path 0 → 2 → 5 → 4 with total weight 20.

35.03.3

Lazy outdated entries

When a vertex's estimate improves, its old queue entry is still there with the larger distance. **Lazy deletion** leaves it: when it is eventually popped, top.distance > dist[v] shows that the vertex was already handled with a smaller value, and the entry is skipped. Every entry is pushed once and popped once.

So the queue holds at most m + 1 entries, and the number of skipped entries equals the number of pushes minus the number of settled vertices. Run the second preset, *Outdated entries appear*, to see one entry marked as skipped.

Java

1static long[] queueStats(int n, List<int[]>[] adj, int s) {       // {entries pushed, entries popped, outdated entries skipped}
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n];
4    Arrays.fill(dist, INF);
5    dist[s] = 0;
6    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
7    pq.add(new long[]{0, s});
8    long pushed = 1, popped = 0, stale = 0;
9    while (!pq.isEmpty()) {
10        long[] top = pq.poll();
11        popped++;
12        int u = (int) top[1];
13        if (top[0] > dist[u]) { stale++; continue; }
14        for (int[] e : adj[u])
15            if (dist[u] + e[1] < dist[e[0]]) {
16                dist[e[0]] = dist[u] + e[1];
17                pq.add(new long[]{dist[e[0]], e[0]});
18                pushed++;
19            }
20    }
21    return new long[]{pushed, popped, stale};
22}

Dijkstra with a priority queue: lazy deletion and path reconstruction

Interactive · edit the input

undirected graph · 6 vertices · 9 edges

d=0

Being settledHas a queue entrySettledTree edge / on the pathOutdated entry skipped

queue {dist, vertex}, smallest first

0,0

dist[v]

∞1

∞2

∞3

∞4

∞5

Setup

Start with {0, 0} in the priority queue. The queue always gives the unsettled vertex with the smallest known distance; with non-negative weights nothing found later can beat it.

Step 1 / 28

Java

1long[] dijkstra(int n, List<int[]>[] adj, int s, int[] parent) {   // adj[u] = {v, w}, all w >= 0
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
4    Arrays.fill(parent, -1);
5    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));   // {distance, vertex}
6    pq.add(new long[]{0, s});
7    while (!pq.isEmpty()) {
8        long[] top = pq.poll(); int u = (int) top[1];
9        if (top[0] > dist[u]) continue;           // outdated entry: u was already improved
10        for (int[] e : adj[u]) {
11            if (dist[u] + e[1] >= dist[e[0]]) continue;
12            dist[e[0]] = dist[u] + e[1]; parent[e[0]] = u;
13            pq.add(new long[]{dist[e[0]], e[0]});   // lazy: the old entry stays in the queue
14        }
15    }
16    return dist;
17}
18List<Integer> pathTo(int[] parent, int t) {       // follow parents back from t
19    LinkedList<Integer> p = new LinkedList<>();
20    for (int v = t; v != -1; v = parent[v]) p.addFirst(v);
21    return p;
22}

Live state

1 entries pushed0 outdated entries skipped

source

No condition evaluated on this step

Execution trace (dry run table)Show 28 steps

Step	Line	State	What happens
1	L6	source=0	Start with {0, 0} in the priority queue. The queue always gives the unsettled vertex with the smallest known distance; with non-negative weights nothing found later can beat it.
2	L8	u=0 dist[u]=0	Pop {0, 0}: the distance to 0 is final (0). Relax its edges.
3	L12	u=0 v=1 dist[v]=7	0 → 1: 0 + 7 = 7. dist[1] = 7, parent[1] = 0, and a new entry {7, 1} is pushed.
4	L12	u=0 v=2 dist[v]=9	0 → 2: 0 + 9 = 9. dist[2] = 9, parent[2] = 0, and a new entry {9, 2} is pushed.
5	L12	u=0 v=5 dist[v]=14	0 → 5: 0 + 14 = 14. dist[5] = 14, parent[5] = 0, and a new entry {14, 5} is pushed.
6	L8	u=1 dist[u]=7	Pop {7, 1}: the distance to 1 is final (7). Relax its edges.
7	L10	u=1 v=0 candidate=14	1 → 0: 7 + 7 = 14 does not beat 0.
8	L10	u=1 v=2 candidate=17	1 → 2: 7 + 10 = 17 does not beat 9.
9	L12	u=1 v=3 dist[v]=22	1 → 3: 7 + 15 = 22. dist[3] = 22, parent[3] = 1, and a new entry {22, 3} is pushed.
10	L8	u=2 dist[u]=9	Pop {9, 2}: the distance to 2 is final (9). Relax its edges.
11	L10	u=2 v=0 candidate=18	2 → 0: 9 + 9 = 18 does not beat 0.
12	L10	u=2 v=1 candidate=19	2 → 1: 9 + 10 = 19 does not beat 7.
13	L12	u=2 v=3 dist[v]=20	2 → 3: 9 + 11 = 20. dist[3] = 20, parent[3] = 2, and a new entry {20, 3} is pushed; the older, larger entry for 3 stays in the queue.
14	L12	u=2 v=5 dist[v]=11	2 → 5: 9 + 2 = 11. dist[5] = 11, parent[5] = 2, and a new entry {11, 5} is pushed; the older, larger entry for 5 stays in the queue.
15	L8	u=5 dist[u]=11	Pop {11, 5}: the distance to 5 is final (11). Relax its edges.
16	L10	u=5 v=0 candidate=25	5 → 0: 11 + 14 = 25 does not beat 0.
17	L10	u=5 v=2 candidate=13	5 → 2: 11 + 2 = 13 does not beat 9.
18	L12	u=5 v=4 dist[v]=20	5 → 4: 11 + 9 = 20. dist[4] = 20, parent[4] = 5, and a new entry {20, 4} is pushed.
19	L9	entry=14,5 dist[v]=11	Pop {14, 5}, but dist[5] is already 11: this entry is outdated (a shorter route was found after it was pushed). Skip it. Skipping instead of deleting is called lazy deletion.
20	L8	u=3 dist[u]=20	Pop {20, 3}: the distance to 3 is final (20). Relax its edges.
21	L10	u=3 v=1 candidate=35	3 → 1: 20 + 15 = 35 does not beat 7.
22	L10	u=3 v=2 candidate=31	3 → 2: 20 + 11 = 31 does not beat 9.
23	L10	u=3 v=4 candidate=26	3 → 4: 20 + 6 = 26 does not beat 20.
24	L8	u=4 dist[u]=20	Pop {20, 4}: the distance to 4 is final (20). Relax its edges.
25	L10	u=4 v=3 candidate=26	4 → 3: 20 + 6 = 26 does not beat 20.
26	L10	u=4 v=5 candidate=29	4 → 5: 20 + 9 = 29 does not beat 11.
27	L9	entry=22,3 dist[v]=20	Pop {22, 3}, but dist[3] is already 20: this entry is outdated (a shorter route was found after it was pushed). Skip it. Skipping instead of deleting is called lazy deletion.
28	L15	return=[0, 7, 9, 20, 20, 11] pushed=8 skipped=2	Distances: [0, 7, 9, 20, 20, 11] (∞ = unreachable). 8 entries pushed, 2 skipped as outdated; each arrow pushes at most one entry (an undirected edge is two arrows), so the cost is O(m log m). Following parents back from 4 gives the path 0 → 2 → 5 → 4 with total weight 20.

35.03.4

Indexed heap

An **indexed heap** keeps at most one entry per vertex and remembers where each vertex sits in the heap array (pos[v]). When an estimate improves, it **decreases the key** in place by sifting the entry up, in O(log n). The heap then never holds more than n entries.

This saves memory and skips the stale pops, at the price of more code. With a binary heap the total time is still O((n + m) log n); the gain is in the constant factor and in memory. A Fibonacci heap reaches O(m + n log n) in theory but is rarely faster in practice.

Java

1static class IndexedMinHeap {                                      // one entry per vertex; decrease-key in O(log n)
2    private final int[] heap, pos;                                 // heap[i] = vertex in slot i; pos[v] = slot of v, -1 if absent
3    private final long[] key;
4    private int size = 0;
5    IndexedMinHeap(int n) { heap = new int[n]; pos = new int[n]; key = new long[n]; Arrays.fill(pos, -1); }
6    boolean isEmpty() { return size == 0; }
7    void pushOrDecrease(int v, long k) {
8        if (pos[v] == -1) { key[v] = k; pos[v] = size; heap[size++] = v; siftUp(pos[v]); }
9        else if (k < key[v]) { key[v] = k; siftUp(pos[v]); }
10    }
11    int popMin() {
12        int top = heap[0];
13        heap[0] = heap[--size];
14        pos[heap[0]] = 0;
15        pos[top] = -1;
16        if (size > 0) siftDown(0);
17        return top;
18    }
19    long keyOf(int v) { return key[v]; }
20    private void siftUp(int i) {
21        while (i > 0 && key[heap[(i - 1) / 2]] > key[heap[i]]) { swap(i, (i - 1) / 2); i = (i - 1) / 2; }
22    }
23    private void siftDown(int i) {
24        while (true) {
25            int l = 2 * i + 1, r = l + 1, m = i;
26            if (l < size && key[heap[l]] < key[heap[m]]) m = l;
27            if (r < size && key[heap[r]] < key[heap[m]]) m = r;
28            if (m == i) return;
29            swap(i, m);
30            i = m;
31        }
32    }
33    private void swap(int a, int b) { int t = heap[a]; heap[a] = heap[b]; heap[b] = t; pos[heap[a]] = a; pos[heap[b]] = b; }
34    static long[] dijkstra(int n, List<int[]>[] adj, int s) {
35        long INF = Long.MAX_VALUE / 2;
36        long[] dist = new long[n];
37        Arrays.fill(dist, INF);
38        dist[s] = 0;
39        IndexedMinHeap heap = new IndexedMinHeap(n);
40        heap.pushOrDecrease(s, 0);
41        while (!heap.isEmpty()) {
42            int u = heap.popMin();
43            for (int[] e : adj[u])
44                if (dist[u] + e[1] < dist[e[0]]) { dist[e[0]] = dist[u] + e[1]; heap.pushOrDecrease(e[0], dist[e[0]]); }
45        }
46        return dist;
47    }
48}

35.03.5

Path reconstruction

Record parent[v] = u whenever an edge u → v lowers dist[v]. When the algorithm ends, parent holds the shortest-path tree. Walk from the target back through parents to the source and reverse the list. If the target's distance is still infinite, there is no path and the result is empty.

Give the animation a destination vertex and the last frame lists the path. For a single target you may stop the search as soon as the target is popped, because its distance is final at that point.

Java

1static List<Integer> shortestPath(int n, List<int[]>[] adj, int s, int t) {   // empty when t is unreachable
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n];
4    int[] parent = new int[n];
5    Arrays.fill(dist, INF);
6    Arrays.fill(parent, -1);
7    dist[s] = 0;
8    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
9    pq.add(new long[]{0, s});
10    while (!pq.isEmpty()) {
11        long[] top = pq.poll();
12        int u = (int) top[1];
13        if (top[0] > dist[u]) continue;
14        if (u == t) break;                                         // the target is settled: its distance is final
15        for (int[] e : adj[u])
16            if (dist[u] + e[1] < dist[e[0]]) {
17                dist[e[0]] = dist[u] + e[1];
18                parent[e[0]] = u;
19                pq.add(new long[]{dist[e[0]], e[0]});
20            }
21    }
22    LinkedList<Integer> path = new LinkedList<>();
23    if (dist[t] >= INF) return path;
24    for (int v = t; v != -1; v = parent[v]) path.addFirst(v);
25    return path;
26}

Dijkstra with a priority queue: lazy deletion and path reconstruction

Interactive · edit the input

undirected graph · 6 vertices · 9 edges

d=0

Being settledHas a queue entrySettledTree edge / on the pathOutdated entry skipped

queue {dist, vertex}, smallest first

0,0

dist[v]

∞1

∞2

∞3

∞4

∞5

Setup

Start with {0, 0} in the priority queue. The queue always gives the unsettled vertex with the smallest known distance; with non-negative weights nothing found later can beat it.

Step 1 / 28

Java

1long[] dijkstra(int n, List<int[]>[] adj, int s, int[] parent) {   // adj[u] = {v, w}, all w >= 0
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
4    Arrays.fill(parent, -1);
5    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));   // {distance, vertex}
6    pq.add(new long[]{0, s});
7    while (!pq.isEmpty()) {
8        long[] top = pq.poll(); int u = (int) top[1];
9        if (top[0] > dist[u]) continue;           // outdated entry: u was already improved
10        for (int[] e : adj[u]) {
11            if (dist[u] + e[1] >= dist[e[0]]) continue;
12            dist[e[0]] = dist[u] + e[1]; parent[e[0]] = u;
13            pq.add(new long[]{dist[e[0]], e[0]});   // lazy: the old entry stays in the queue
14        }
15    }
16    return dist;
17}
18List<Integer> pathTo(int[] parent, int t) {       // follow parents back from t
19    LinkedList<Integer> p = new LinkedList<>();
20    for (int v = t; v != -1; v = parent[v]) p.addFirst(v);
21    return p;
22}

Live state

1 entries pushed0 outdated entries skipped

source

No condition evaluated on this step

Execution trace (dry run table)Show 28 steps

Step	Line	State	What happens
1	L6	source=0	Start with {0, 0} in the priority queue. The queue always gives the unsettled vertex with the smallest known distance; with non-negative weights nothing found later can beat it.
2	L8	u=0 dist[u]=0	Pop {0, 0}: the distance to 0 is final (0). Relax its edges.
3	L12	u=0 v=1 dist[v]=7	0 → 1: 0 + 7 = 7. dist[1] = 7, parent[1] = 0, and a new entry {7, 1} is pushed.
4	L12	u=0 v=2 dist[v]=9	0 → 2: 0 + 9 = 9. dist[2] = 9, parent[2] = 0, and a new entry {9, 2} is pushed.
5	L12	u=0 v=5 dist[v]=14	0 → 5: 0 + 14 = 14. dist[5] = 14, parent[5] = 0, and a new entry {14, 5} is pushed.
6	L8	u=1 dist[u]=7	Pop {7, 1}: the distance to 1 is final (7). Relax its edges.
7	L10	u=1 v=0 candidate=14	1 → 0: 7 + 7 = 14 does not beat 0.
8	L10	u=1 v=2 candidate=17	1 → 2: 7 + 10 = 17 does not beat 9.
9	L12	u=1 v=3 dist[v]=22	1 → 3: 7 + 15 = 22. dist[3] = 22, parent[3] = 1, and a new entry {22, 3} is pushed.
10	L8	u=2 dist[u]=9	Pop {9, 2}: the distance to 2 is final (9). Relax its edges.
11	L10	u=2 v=0 candidate=18	2 → 0: 9 + 9 = 18 does not beat 0.
12	L10	u=2 v=1 candidate=19	2 → 1: 9 + 10 = 19 does not beat 7.
13	L12	u=2 v=3 dist[v]=20	2 → 3: 9 + 11 = 20. dist[3] = 20, parent[3] = 2, and a new entry {20, 3} is pushed; the older, larger entry for 3 stays in the queue.
14	L12	u=2 v=5 dist[v]=11	2 → 5: 9 + 2 = 11. dist[5] = 11, parent[5] = 2, and a new entry {11, 5} is pushed; the older, larger entry for 5 stays in the queue.
15	L8	u=5 dist[u]=11	Pop {11, 5}: the distance to 5 is final (11). Relax its edges.
16	L10	u=5 v=0 candidate=25	5 → 0: 11 + 14 = 25 does not beat 0.
17	L10	u=5 v=2 candidate=13	5 → 2: 11 + 2 = 13 does not beat 9.
18	L12	u=5 v=4 dist[v]=20	5 → 4: 11 + 9 = 20. dist[4] = 20, parent[4] = 5, and a new entry {20, 4} is pushed.
19	L9	entry=14,5 dist[v]=11	Pop {14, 5}, but dist[5] is already 11: this entry is outdated (a shorter route was found after it was pushed). Skip it. Skipping instead of deleting is called lazy deletion.
20	L8	u=3 dist[u]=20	Pop {20, 3}: the distance to 3 is final (20). Relax its edges.
21	L10	u=3 v=1 candidate=35	3 → 1: 20 + 15 = 35 does not beat 7.
22	L10	u=3 v=2 candidate=31	3 → 2: 20 + 11 = 31 does not beat 9.
23	L10	u=3 v=4 candidate=26	3 → 4: 20 + 6 = 26 does not beat 20.
24	L8	u=4 dist[u]=20	Pop {20, 4}: the distance to 4 is final (20). Relax its edges.
25	L10	u=4 v=3 candidate=26	4 → 3: 20 + 6 = 26 does not beat 20.
26	L10	u=4 v=5 candidate=29	4 → 5: 20 + 9 = 29 does not beat 11.
27	L9	entry=22,3 dist[v]=20	Pop {22, 3}, but dist[3] is already 20: this entry is outdated (a shorter route was found after it was pushed). Skip it. Skipping instead of deleting is called lazy deletion.
28	L15	return=[0, 7, 9, 20, 20, 11] pushed=8 skipped=2	Distances: [0, 7, 9, 20, 20, 11] (∞ = unreachable). 8 entries pushed, 2 skipped as outdated; each arrow pushes at most one entry (an undirected edge is two arrows), so the cost is O(m log m). Following parents back from 4 gives the path 0 → 2 → 5 → 4 with total weight 20.

Practice ladder

Now try it yourself

Easy

Network Delay Time

Medium

Path with Maximum Probability
Path With Minimum Effort
Cheapest Flights Within K Stops
Swim in Rising Water

Advanced

Minimum Cost to Reach Destination in Time
Shortest Path Visiting All Nodes
Reachable Nodes In Subdivided Graph

Key takeaways

Dijkstra settles the closest unsettled vertex; this is safe only when no weight is negative.
With a binary heap and lazy deletion the cost is O((n + m) log n); the quadratic version suits dense graphs.
Outdated entries are skipped when popped; pushes equal pops.
An indexed heap supports decrease-key and holds one entry per vertex.
Parent links give the path; stop early when the target is popped.