Dijkstra's Algorithm

Finds the shortest path between nodes in a graph with non-negative weights.

Step 1 of 13

Initialise. Distance to "A" = 0; all others = ∞.

Distances

A	0
B	∞
C	∞
D	∞
E	∞

Priority Queue

Adist = 0

▶Algorithm

dist[s] = 0; dist[v] = ∞ for all v ≠ s
enqueue (s, 0)
while queue not empty:
u ← extract-min(); mark settled
for each neighbor v of u:
if dist[u] + w(u,v) < dist[v]:
  dist[v] = dist[u] + w; enqueue v
// all reachable nodes settled

Legend

Settling (active)

In queue

Settled ✓

Numbers below nodes show current shortest distance from A.

1 / 13Speed