Shortest Paths as Relaxation Schedules

Bellman–Ford, Dijkstra, min-plus propagation, and max-plus critical paths

A shortest-path label is a promise about the best path found so far. Relaxation tests whether one more edge improves that promise.

Add along a path. Take the minimum across alternatives. Algorithms differ only in how they schedule those comparisons.

Graph

Mode

Playback

Speed

Distance labels

Current step

—

Event log

Duality: max-plus is min-plus in the mirror

min(−a, −b) = −max(a, b)        x ↦ −x,   +∞ ↔ −∞

	S	A	B	C	D	T
max-plus e on w	0	3	1	6	9	10
min-plus d on −w	0	−3	−1	−6	−9	−10

Negate every weight and run the min-plus machinery of the other modes: you get exactly d = −e. Longest-path and critical-path problems are shortest-path problems through the mirror — which is why every algorithm on this page needed only one new line: swap min for max.

Legend

Unreached — distance is ∞

Tentative — reachable, not final

Settled / reached earlier

Newly reached or improved

Relaxation improved a label

Relaxation tested, did not win

−∞ — not yet constrained (critical-path mode)

Final path at completion (shortest or critical)

Dashed blue — reached by an earlier power; the exactly-k wave has moved past (raw W only)

Green ring — zero slack: on the critical path (CPM)

L= / s= under a node — latest start / slack (CPM backward pass)

Distance labels

Current step

Event log

Bellman–Ford Step ›

Dijkstra Step ›

Bellman–Ford

Dijkstra