Dijkstra's Shortest Path

Step-by-step greedy relaxation on a weighted graph

Initialise

Graph Traversal

Active Relaxed Shortest path

Hover a node in the distance table to highlight its shortest path

Priority Queue (unvisited nodes, sorted by dist)

A0

B∞

C∞

D∞

E∞

F∞

#Initialising: distance to source node A = 0. All others = ∞.

Speed900ms

Progress1/32

Live Stats

Settled

0

Remaining

6

Distance Table

A

via —

0

B

via —

∞

C

via —

∞

D

via —

∞

E

via —

∞

F

via —

∞

Algorithm

Dijkstra's finds the shortest path from a source to all nodes in O((V + E) log V).

Always pick the unvisited node with smallest known distance.