Medium difficulty · Algorithm · Topics: graph, dijkstra, shortest-path, heap
Dijkstra's algorithm finds the shortest distance from one source vertex to every other vertex in a graph whose edge weights are all non-negative. It returns an array dist where dist[v] is the cost of the cheapest path from the source to v.
Picture a fire spreading from the source along roads, where each road burns for as long as its weight. The fire reaches vertices in order of true distance, so the first time it reaches a vertex is by its shortest route. Dijkstra simulates this: a min-heap always hands back the unfinished vertex with the smallest known distance, and that distance is final, because every other route to it would have to pass through a vertex that is at least as far away and then add a non-negative weight.
That is also why negative edges break it: a later, longer-looking route could become cheaper after a negative edge, but Dijkstra has already declared the vertex finished and never reconsiders it.
dist to Infinity except dist[source] = 0, and put [0, source] in the min-heap.dnoded > dist[node], this entry is stale (a better one was already processed); skip it. The heap has no decrease-key, so outdated entries are simply left in and ignored when they surface.node -> next with weight, if d + weight < dist[next], update dist[next] and push [dist[next], next].dist.Test case 0: n = 5, undirected edges [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]], source 0.
Pop [d, node] | Action | dist after |
|---|---|---|
[0, 0] | relax 1 -> 4, 2 -> 1 | [0,4,1,Inf,Inf] |
[1, 2] | relax 1 -> 3 (better than 4), 3 -> 6 | [0,3,1,6,Inf] |
[3, 1] | relax 3 -> 4 (better than 6) | [0,3,1,4,Inf] |
[4, 1] | stale (4 > 3), skipped | unchanged |
[4, 3] | relax 4 -> 7 | [0,3,1,4,7] |
[6, 3] | stale (6 > 4), skipped | unchanged |
[7, 4] | nothing to improve | [0,3,1,4,7] |
The result is [0, 3, 1, 4, 7]. Note how vertex 1 first looked like 4 away, and was improved to 3 through vertex 2.
| Time | Space | Reason | |
|---|---|---|---|
| Binary heap (this code) | O((V + E) log V) | O(V + E) | Each edge can push one heap entry (log) and the heap and adjacency list store O(E) items. |
| Array instead of heap | O(V^2) | O(V) | Scanning for the minimum each round; better only for very dense graphs. |
parent for each vertex whenever you relax it.Infinity; handle that before using the value.dist to a "large" number that can overflow when you add a weight.Follow pq (the heap) and dist: each relaxation changes one dist slot and adds a heap entry. Watch d and node after every pop, and look for the pops that hit continue (stale entries). In the node-link view of adj, node and next mark the edge being relaxed.
Input: n = 5, edges = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [3, 4, 3]], source = 0
Output: [0, 3, 1, 4, 7]
class Solution {
dijkstra(n, edges, source) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) {
adj[u].push([v, w]);
adj[v].push([u, w]);
}
const dist = new Array(n).fill(Infinity);
dist[source] = 0;
// min-heap ordered by distance; entries are [distance, vertex]
const pq = new PriorityQueue((a, b) => a[0] - b[0]);
pq.enqueue([0, source]);
while (!pq.isEmpty()) {
const [d, node] = pq.dequeue();
if (d > dist[node]) continue; // stale entry: a shorter route was already found
for (const [next, weight] of adj[node]) {
// relaxation: is going through node shorter than the best known route to next?
if (d + weight < dist[next]) {
dist[next] = d + weight;
pq.enqueue([dist[next], next]);
}
}
}
return dist;
}
}