Dijkstra's Shortest Path — Animate | AI Wisdom

← Back to topic
🎞 ANIMATE · Mode 3 of 5 · +100 XP— Dijkstra's Algorithm
🗺️Init
🔄Relax
📌Settle
🏁Done
🎯 Next: Test →
Step 1 / 4
Speed
Initialise distances
Set dist[A]=0, all others=∞. Add A to priority queue💡 Analogy
Like GPS: you know where you are (distance 0), everything else is unknown.
Start with distance 0 for the source. All others are unknown (∞). Queue contains [A, 0].
Console Output
> dist: {A:0, B:∞, C:∞, D:∞}
> pq: [[0,A]]
●dijkstra.ts
Initialise distancesL4–7
1function dijkstra(graph: Record<string, [string, number][]>, start: string) {
2  const dist: Record<string, number> = {};
3  const visited = new Set<string>();
4  const pq: [number, string][] = [[0, start]]; // [distance, node]
5 
6  for (const node in graph) dist[node] = Infinity;
7  dist[start] = 0;
8 
9  while (pq.length > 0) {
10    pq.sort((a, b) => a[0] - b[0]);          // Min-heap simulation
11    const [d, u] = pq.shift()!;
12 
13    if (visited.has(u)) continue;
14    visited.add(u);
15 
16    for (const [v, weight] of graph[u]) {
17      if (dist[u] + weight < dist[v]) {
18        dist[v] = dist[u] + weight;           // Relaxation
19        pq.push([dist[v], v]);
20      }
21    }
22  }
23  return dist;
24}
25 
26// A→B:4, A→C:2, B→D:3, C→B:1, C→D:5
27const g = { A:[['B',4],['C',2]], B:[['D',3]], C:[['B',1],['D',5]], D:[] };
28dijkstra(g, 'A'); // → {A:0, B:3, C:2, D:6}
28 lines
Timeline — 4 Steps
Initialise distances
Set dist[A]=0, all others=∞. Add A to priority queue💡 Analogy
Like GPS: you know where you are (distance 0), everything else is unknown.
Start with distance 0 for the source. All others are unknown (∞). Queue contains [A, 0].
Console Output
> dist: {A:0, B:∞, C:∞, D:∞}
> pq: [[0,A]]

Set dist[A]=0, all others=∞. Add A to priority queue

Set dist[A]=0, all others=∞. Add A to priority queue

Was this page helpful?

Discussion

Set dist[A]=0, all others=∞. Add A to priority queue

Set dist[A]=0, all others=∞. Add A to priority queue

Was this page helpful?

Discussion