Problem overview
The method dijkstra receives n, the number of vertices labeled 0 to n - 1, and a list of edges, where each edge is [u, v, weight]. The graph is undirected and connected, and all weights are positive. The method returns an array dist where dist[i] is the length of the shortest path from vertex 0 to vertex i, the length being the sum of the edge weights.
In the example, n = 5 and edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]]. The direct edge from 0 to 1 costs 4, but going through vertex 2 costs 1 + 2 = 3. Vertex 3 is best reached through 1, for 3 + 1 = 4, and vertex 4 through 3, for 4 + 3 = 7. The answer is [0, 3, 1, 4, 7].
Approach: always settle the closest unsettled vertex
With equal weights, a breadth-first search finds shortest paths, because the fewest edges means the shortest distance. With different weights it doesn't: in the example, the one-edge path to vertex 1 (cost 4) is longer than the two-edge path (cost 3).
Dijkstra's algorithm fixes this with one rule: always process the vertex with the smallest known distance next. Because every weight is positive, once the closest unprocessed vertex is taken from the queue, no later path can reach it more cheaply, since any other route must pass through a vertex that is at least as far. Its distance is final.
Processing a vertex means relaxing its edges. For each neighbour v with edge weight w, ask whether going through the current vertex u is better than the best distance known for v. If dist[u] + w < dist[v], update dist[v] and add v to the queue with its new distance.
The queue holds [distance, vertex] pairs and always hands out the smallest distance. TypeScript has no built-in priority queue, so this lesson uses an array that it sorts before every removal. That is simple to write and fast enough for 1,000 vertices.
The queue is never edited in place. When a shorter route to a vertex is found, a new pair is pushed, and the old, longer pair stays behind. When an old pair is finally removed, its distance is larger than the stored dist for that vertex, so it is recognised as outdated and skipped. This is sometimes called lazy deletion.
Step by step
- Build the adjacency list.
adjhas typenumber[][][]: for each vertex, a list of[neighbour, weight]pairs.Array.fromwith a factory gives each vertex its own list. - Add each edge in both directions. Destructure every edge into
u,vandw, and push[v, w]ontoadj[u]and[u, w]ontoadj[v], because the graph is undirected. - Create
distfilled withInfinityfor "not reached", and setdist[0]to 0. - Create the queue
pqas anumber[][]that starts with[0, 0]: distance first, vertex second, so that sorting by the first element sorts by distance. - Loop while
pqhas entries. - Sort and take the closest. Sort
pqbya[0] - b[0], remove the first pair withshift(), and destructure it intodandu. The!aftershift()tells the compiler the loop condition guarantees a pair. Ifd > dist[u], the pair is outdated, socontinue. - Walk the neighbours of
uwith afor...ofloop that destructures each entry intovandw. - Relax. If
dist[u] + w < dist[v], setdist[v]to the smaller value and push[dist[v], v]. Pushing only on a real improvement keeps the queue short. - Return
dist. When the queue is empty, every distance is final.
The solution in TypeScript
class Solution {
dijkstra(n: number, edges: number[][]): number[] {
const adj: number[][][] = Array.from({length: n}, () => []);
for (const [u, v, w] of edges) {
adj[u].push([v, w]);
adj[v].push([u, w]);
}
const dist: number[] = new Array(n).fill(Infinity);
dist[0] = 0;
const pq: number[][] = [[0, 0]];
while (pq.length > 0) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u] = pq.shift()!;
if (d > dist[u]) {
continue;
}
for (const [v, w] of adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push([dist[v], v]);
}
}
}
return dist;
}
}
Details worth knowing:
- The comparator is required. Without one,
sort()compares elements as strings. For numbers,[10, 9, 1].sort()gives[1, 10, 9], so a distance of 10 would be taken before 9. The comparator(a, b) => a[0] - b[0]compares the distances as numbers. Infinityis a number. It is larger than every finite value, so the first real path always beats it, andInfinity + wnever comes up here because only vertices taken from the queue are relaxed. Numbers also don't overflow at these sizes: path lengths stay far below 2^53.- Destructuring.
for (const [v, w] of adj[u])andconst [d, u] = pq.shift()!unpack the pairs. The!is erased when the code is compiled; it only quiets the type checker. - Methods and locals. Everything happens inside one method, so there are no
thiscalls. The queue anddistare local to each call. - The stale-entry check uses
>. An entry withd === dist[u]is the current best and must be processed. Only strictly larger distances are outdated.
Complexity
Let V be the number of vertices and E the number of edges.
Time. Each successful relaxation adds one pair to the queue, so the queue sees at most 2E pushes. With a real priority queue (a binary heap), each push and removal costs O(log E), giving O((V + E) log V) overall. This lesson's version sorts the whole queue before every removal. A sort of k pairs costs O(k log k), so the total is higher, roughly O(E² log E) in the worst case. That is a poor fit for big graphs, but it works for the limits here (1,000 vertices and 5,000 edges). On a random graph of that size it finished in well under a second in a test run. Replacing the array with a heap is the standard upgrade.
Space: O(V + E). The adjacency list stores every edge twice, dist has V entries, and the queue holds at most one pair per relaxation.
Edge cases and common mistakes
- A shorter route with more edges. With
n = 4andedges = [[0,1,10],[0,2,3],[2,1,2],[1,3,1]], vertex 1 is first assigned 10, then improved to 5 through vertex 2. The answer is[0, 5, 3, 6]. - Stale entries. With
edges = [[0,1,5],[0,2,1],[2,1,1]]andn = 3, vertex 1 is pushed with distance 5 and later with 2. The pair with 5 comes out last and is skipped. The result is[0, 2, 1]. - The edge's order doesn't matter.
n = 2with[[1,0,7]]gives[0, 7], because each edge is stored in both directions. - Negative weights. The correctness argument depends on weights being positive, which the constraints guarantee. With negative weights, a vertex's distance could still drop after it was processed.
- Unreachable vertices. The statement says the graph is connected. If it weren't, unreached vertices would stay at
Infinity. - Forgetting to store both directions. The search would only follow edges in the order they are listed.
- Skipping the stale check. The answer would still be right, because outdated pairs relax nothing, but each one would be re-expanded and the running time would grow.
Testing
n = 5,edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]]gives[0, 3, 1, 4, 7].n = 2,edges = [[1,0,7]]gives[0, 7].n = 4,edges = [[0,1,10],[0,2,3],[2,1,2],[1,3,1]]gives[0, 5, 3, 6].n = 3,edges = [[0,1,5],[0,2,1],[2,1,1]]gives[0, 2, 1].