The greedy shortest path. Keep a tentative distance to every node; repeatedly finalize the unvisited node with the smallest tentative distance and relax its out-edges. Because every weight is non-negative, the node you just popped can never be improved later — so its distance is final the moment it leaves the frontier. Down the center, data flows: the weighted graph goes in, the frontier decides, the shortest-path tree comes out. The blue team builds and proves it against brute force; the red team tries to break it.
source Dijkstra, E. W., A Note on Two Problems in Connexion with Graphs (1959), Numerische Mathematik 1, 269–271 — doi.org/10.1007/BF01386390. Rendered, not quoted.
Validity is not asserted; it is computed. For the current source, this is the live shortest-path tree: each node's final distance, the parent it was relaxed from, and the order it was popped from the frontier.
Distances are green when they match a brute-force minimum over all simple paths, red when they do not.
| node | dist | parent | pop # |
|---|
Dijkstra 1959 is the greedy shortest path: it works precisely because weights are non-negative. Drop that condition and you need its slower cousin, the-bellman-ford, which relaxes every edge |V|−1 times and detects negative cycles.
Add a goal-directed lower-bound heuristic to the same frontier and you get the-a-star; leave the heuristic at zero and A* is Dijkstra. The very same priority frontier runs the shortest-path core of routing protocols (OSPF, IS-IS). Each sphere is the next one's premise.
The blue team's live check: re-run Dijkstra from A over the whole graph and confirm every distance equals the brute-force minimum. If red tampers with the pop order, this badge is where it shows.
A directed graph on 6 nodes with non-negative edge weights. Dijkstra assumes nothing else — no coordinates, no heuristic, just the arcs and their costs. The trap is deliberate: the direct arc A→B costs 4, but A→C→B costs only 2, so the shortest route to B is discovered after B is first seen.
| edge | weight |
|---|
These arcs are what you feed the panel below.
Pick a source and target; the engine runs a min-priority frontier, finalizes nodes in nondecreasing distance, and recovers the path from the parent tree.
Mode: greedy — the frontier always pops the smallest tentative distance.
Change source or target — the path and its cost are computed on the spot and checked against brute force, never looked up.
What the machine produces, proven: single-source shortest distances to all nodes, matched exactly against a brute-force search over every simple path — from A the tree is A0 · C1 · B2 · D3 · E4 · F5. The greedy invariant holds: every popped node's distance is already final.
The blue team's witness (left) confirms these distances live; the red team (right) tries to make them wrong.
It is also single-source only, needs the whole graph in memory, and a naive array scan is O(V²) — respectable but beaten by a heap. "Greedy is correct" is a choice licensed only by non-negativity, which is why the graveyard keeps a negative-edge counterexample.
"Dijkstra works on any weighted graph." Cut. Only for non-negative weights. On A→B:1, A→C:2, C→B:−2 it finalizes B at 1 while the true shortest is 0 — computed live in the self-check.
"Dijkstra finds the path between two nodes." Refined. It computes shortest paths from one source to every node; you may stop early once the target is popped.
"Dijkstra is O(V²)." Kept, corrected. That is the array version. A binary heap gives O((V+E) log V); a Fibonacci heap O(E + V log V).
The red team's move: finalize nodes in insertion (FIFO) order instead of by minimum tentative distance. A shorter path discovered later is then ignored — the greedy invariant is gone.
Switch to FIFO and node B finalizes at 4 (via A→B) before A→C→B=2 is found — distances no longer match brute force. The witness (window 7) recomputes, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.