Problem overview
The method dijkstra receives n, the number of vertices (labeled 0 to n - 1), and a list of edges of a weighted, undirected graph. Each edge is [u, v, weight] with a weight from 1 to 1000. It returns an array dist of length n in which dist[i] is the length of the shortest path from vertex 0 to vertex i, where the length of a path is the sum of its edge weights. The graph is connected, so every vertex can be reached.
For n = 5 and edges = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [3, 4, 3]] the answer is [0, 3, 1, 4, 7]. The direct edge from 0 to 1 costs 4, but going 0 to 2 to 1 costs 1 + 2 = 3, which is shorter. Vertex 3 is best reached through 1, for a total of 4, and vertex 4 hangs off vertex 3, giving 7.
Approach: settle the closest unsettled vertex, then relax its edges
Breadth-first search finds shortest paths when every edge counts as 1. With weights, the path with the fewest edges is not necessarily the cheapest, as the example shows: the one-edge route to vertex 1 costs 4, but a two-edge route costs 3.
Dijkstra's algorithm handles positive weights with a simple rule: always process the unsettled vertex with the smallest known distance. Because every weight is positive, no route that goes through a farther vertex can come back to arrive earlier. So when a vertex is the closest one still waiting, its distance can no longer improve, and it is final.
The algorithm keeps a dist array of the best distances found so far, starting at infinity for everything except the source. When a vertex u is processed, it looks at each edge (u, v, w) and asks whether going through u is better: is dist[u] + w less than the current dist[v]? If so, dist[v] is lowered. This step is called relaxation.
To find the closest waiting vertex quickly, textbook versions use a priority queue (a heap). JavaScript has no built-in one, so this lesson uses a plain array of [distance, vertex] pairs, sorted by distance before every removal. That is slower than a heap but short to write and fast enough for 1,000 vertices and 5,000 edges.
The queue is never edited in place. When a shorter path to a vertex is found, a new entry is added and the old one stays. The old entry is recognised and skipped when it comes out, which is known as lazy deletion.
Step by step
- Create the adjacency list
adjwithArray.from({length: n}, () => []), so each vertex has its own empty list. - Fill it from the edges. For each edge, unpack
u,vandw, then push[v, w]ontoadj[u]and[u, w]ontoadj[v]. The graph is undirected, so both endpoints must see the edge. - Create
distwithnew Array(n).fill(Infinity)and setdist[0] = 0.conststops the name from being reassigned, but the elements can still change. - Create the queue
pqholding one pair,[0, 0]: distance first, vertex second. Putting the distance first makes it easy to sort by it. - Loop while
pqis not empty. - Sort and take the closest. Sort
pqwith(a, b) => a[0] - b[0], then remove the first pair withshift()and unpack it intodandu. - Skip stale entries. If
d > dist[u], a shorter path touwas found after this entry was queued, anduhas already been handled with the better value. Usecontinueto go to the next entry. - Visit the neighbors. Loop over
adj[u], unpacking each pair intovandw. - Relax. If
dist[u] + w < dist[v], setdist[v]to that sum and push[dist[v], v]ontopq. Adding an entry only on a real improvement keeps the queue from filling with useless entries. - Return
dist. Once the queue is empty, every distance is final.
Tracing the example: the queue starts as [[0, 0]]. Processing vertex 0 sets dist[1] = 4 and dist[2] = 1. The closest entry is now [1, 2]. From vertex 2, going to 1 costs 1 + 2 = 3, which beats 4, and vertex 3 gets 6. Next comes [3, 1], whose edge to vertex 3 gives 3 + 1 = 4, beating 6. The old entries [4, 1] and [6, 3] are stale and skipped when they come out. Vertex 3 then sets dist[4] = 7, and the result is [0, 3, 1, 4, 7].
The solution in JavaScript
class Solution {
/**
* @param {number} n
* @param {number[][]} edges
* @return {number[]}
*/
dijkstra(n, edges) {
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[0] = 0;
const pq = [[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;
}
}
JavaScript details worth knowing:
- The sort comparator. Without a comparator,
sortconverts elements to strings and compares them as text. Sorting plain distances that way puts 10 before 9, and sorting pairs compares strings like"10,3"and"9,2". The comparatora[0] - b[0]compares the numbers themselves. Infinity. It is a real number value larger than any other number, andInfinity + wis stillInfinity. This makes it a safe "not reached yet" marker: any real path length is smaller. If a vertex were unreachable, its entry would stayInfinity, but this lesson guarantees a connected graph.- Destructuring.
const [d, u] = pq.shift()andfor (const [v, w] of adj[u])unpack small arrays into named values, which keeps the pair layout from showing up as[0]and[1]everywhere. - Stable sort. Modern JavaScript sorts are stable, so entries with equal distance keep their order. Dijkstra gives correct distances whatever order ties are processed in.
continue. It ends the current pass of thewhileloop and moves on to the next one, which is the clean way to skip the stale entry.
Complexity
Let V be the number of vertices and E the number of edges.
Time with a heap: O((V + E) log V). This is the standard bound when the queue is a real priority queue. Each successful relaxation adds one entry, so at most 2E entries are ever added, and each costs O(log) to insert and remove.
Time in this solution. Sorting the whole queue before each removal costs O(k log k) for a queue of size k, and the queue can hold up to about E entries. In the worst case the total grows to roughly O(E² log E). The lesson's limits make that acceptable, but a heap would be needed for much larger graphs.
Space: O(V + E). The adjacency list holds every edge twice, dist has one slot per vertex, and the queue holds at most one entry per successful relaxation.
Edge cases and common mistakes
- Negative weights. The algorithm relies on all weights being positive. With a negative weight, a vertex marked as final could still be improved later. The lesson's weights start at 1.
- A shortcut through more edges. The cheapest route can use more edges than the direct one, as vertex 1 shows in the example. Stopping at the first path found, as BFS does, gives wrong answers.
- Forgetting the reverse edge. The graph is undirected. Without
adj[v].push([u, w]), the edge[1, 0, 5]would be invisible from vertex 0, so vertex 1 could not be reached through it. - Missing the stale-entry check. The answer would still be right, because outdated entries cannot relax anything, but the same vertex would be processed several times and the running time would grow.
- Default sort.
pq.sort()with no comparator orders the pairs as text, so a distance of 10 would sort before 9 and the algorithm could process vertices out of order. - Sharing the adjacency lists.
new Array(n).fill([])would use one list for every vertex.Array.fromwith a function creates separate ones. - Source alone. The distance to vertex 0 is always 0, even in a graph with many vertices.
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 = [[0, 1, 7]]gives[0, 7].n = 3,edges = [[0, 1, 5], [1, 2, 5], [0, 2, 20]]gives[0, 5, 10].n = 3,edges = [[1, 0, 5], [2, 1, 1]]gives[0, 5, 6].