Build the graph out of string: every edge is a thread whose length is its weight, every vertex is a
knot where the threads are tied together. The whole thing lies crumpled on the floor. Now grab the
source s and pull it up. Gravity does the rest: each knot sinks as far as its threads allow,
so the knot v ends up exactly d(v) below s, and the threads that end up
taut are precisely the edges on shortest paths — they carry the load. Everything else dangles loose.
The pull height H is Dijkstra's clock: a knot leaves the ground at the very moment
H = d(v), so the knots take off in exactly the order the priority queue settles them.
Hover a knot to light up its shortest path, hover a thread to see why it is taut or slack.
| pull the source up to height H | the key currently being extracted |
| a knot leaves the floor | deleteMin: v is settled, dist[v] final |
| depth of v below the hand | dist[v] |
| thread u–v is taut | dist[u] + w(u,v) = dist[v] (tight) |
| thread u–v hangs slack | dist[u] + w(u,v) > dist[v] (no relaxation) |
| knot never leaves the floor | dist[v] = ∞ (unreachable) |
EdgeWeightedGraph): first line the number of vertices
V, second line the number of edges E, then E lines
v w weight with weight ≥ 0. Vertices are 0 … V−1.
EdgeWeightedDigraph) still loads — the two directions of a pair are merged into one
thread, keeping the smaller weight.
V more lines of x y
— one pair per vertex, in order — to pin down how the graph lies on the floor. This is the
same augmented format the graph editor writes, so prepared graphs carry over. Any numeric scale works;
it is auto-centred and scaled, preserving relative position and aspect ratio.