Pattern visualizer
Dijkstra's Algorithm
Because every edge weight is non-negative, the unvisited vertex with the smallest tentative distance can never be beaten later by a longer path through something still unvisited — so it is safe to lock that vertex's distance in for good right now. That is the whole algorithm: repeatedly pick the closest unlocked vertex, freeze it, and use it to shrink its neighbors' distances (relaxation). The badge on each vertex below is its current best-known distance from the source; the highlighted vertex is the one just locked in, and the highlighted arrows show which distances it just improved. Animated on: 6 vertices, directed weighted edges 0->1(4), 0->2(1), 2->1(2), 1->3(1), 2->3(5), 3->4(3), 1->4(8), 4->5(2), 3->5(6), source = 0 — find the shortest distance from 0 to every other vertex..
Always lock in the closest unvisited vertex, then relax its edges
Distances start at infinity, source at 0
Every vertex starts at infinity except the source, vertex 0, which starts at 0 — that is the only distance we know for certain before looking at a single edge.
1FUNCTION dijkstra(graph, source):2 dist[source] <- 03 FOR EACH v != source4 dist[v] <- INFINITY5 visited <- EMPTY SET6 IF NO unvisited v WHERE dist[v] < INFINITY: RETURN dist7 WHILE visited != ALL vertices8 u <- unvisited v WITH MIN dist[v]9 ADD u TO visited10 FOR EACH (u, v, w) IN edges11 IF dist[u] + w < dist[v]12 dist[v] <- dist[u] + w13 RETURN dist
← / → step · space play · Home restart