1. Source distance
Distance to the start node is zero; all others begin at Infinity.
dist[start] = 0Typorithm · hard
Dijkstra
▷ Interactive algorithm labdijkstragraph-algorithmsshortest-pathgreedyrelaxation
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Dijkstra
Graph Algorithms
Greedily finalize the closest unfinished node, then relax its edges — for non-negative weights.
Dijkstra finds shortest paths from one source in a weighted graph with non-negative edges.
Each round it finalizes the nearest unsettled node, knowing no later path can beat it.
Relaxing that node's edges may lower its neighbors' tentative distances.
Preparing algorithm lab…
01
Finalize the closest node each round.
02
Relax: dist[u] + w < dist[next].
03
Requires non-negative weights.
function dijkstra(graph, n, start) {
const dist = new Array(n).fill(Infinity);
dist[start] = 0;
const done = new Array(n).fill(false);
for (let i = 0; i < n; i += 1) {
let u = -1;
for (let v = 0; v < n; v += 1) {
if (!done[v] && (u === -1 || dist[v] < dist[u])) u = v;
}
if (dist[u] === Infinity) break;
done[u] = true;
for (const [next, weight] of graph[u]) {
if (dist[u] + weight < dist[next]) {
dist[next] = dist[u] + weight;
}
}
}
return dist;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Pick closest
Greedily choose the unfinished node with the smallest known distance.
if (!done[v] && (u === -1 || dist[v] < dist[u])) u = v3. Finalize
Once chosen, that node's shortest distance is settled forever.
done[u] = true4. Relax edge
If going through u is shorter, update the neighbor's distance.
if (dist[u] + weight < dist[next])5. Update distance
Record the better distance found through u.
dist[next] = dist[u] + weightA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.