Shortest Paths as Relaxation Schedules
Shortest-path algorithms can look very different on the page, yet they all do the same small thing over and over: relax an edge — test whether reaching a node through one more step gives a shorter distance, and keep the better value. What distinguishes the classic algorithms is not the update itself but the schedule they use to apply it.
This page compares four views of that single idea:
- Bellman–Ford applies the update in synchronous global sweeps. After sweep r, every label holds the best distance using at most r edges.
- Dijkstra applies it in priority order, finalizing the nearest unsettled node first — valid precisely because edge weights are nonnegative.
- Min-plus (tropical) powers show the same recurrence as matrix–vector propagation: a Bellman–Ford sweep is the product \(A^{\mathsf{T}} \otimes d\).
- Max-plus critical paths flip the semiring: the same propagation with \(\max\) instead of \(\min\) turns the graph into a precedence network and computes earliest start times, the makespan, and the critical path.
Add along a path. Take the minimum across alternatives. Algorithms differ in how they schedule those comparisons.
The explorer is a single self-contained HTML file. It runs entirely in your browser with no server, no network, and no dependencies — so the Download offline HTML link above gives you the same artifact to keep and open directly from disk.
What you can do
- Switch between a paper example graph (six nodes, clean min-plus powers) and a richer teaching graph that exposes tentative-label improvements and wavefronts.
- Watch a single relaxation in full arithmetic detail.
- Step or play Bellman–Ford and Dijkstra, with a live distance table and an explanation panel for every action.
- See min-plus matrix powers on the paper graph, connecting algorithm to algebra.
- Flip the paper graph into a precedence network and watch max-plus propagation compute earliest start times and highlight the critical path \(S \to A \to D \to T\) — the same edges that give shortest path 6 give makespan 10 — then continue into the backward CPM pass: latest starts, slack, and why zero-slack tasks form the critical path.
- Toggle min-plus powers to the raw matrix W and watch the exactly-\(k\) wave pass through the graph and vanish — the demonstration of why the zero diagonal of \(A = I \oplus W\) is what lets labels persist.
- Switch Bellman–Ford to in-place sweeps and reorder the edges: topological order finishes either graph in one sweep, while reversed order degrades exactly to the synchronous wavefront.
- Run Bellman–Ford vs. Dijkstra side by side to compare how they schedule the same work.
Supporting information
This interactive page is intended to serve as supporting information for a tropical-algebra paper, When Addition Becomes Optimization: Tropical Algebra, Paths, Schedules, and Semiring Computation. It is designed to remain usable offline and to be archived on Zenodo alongside the paper.