Math
Graph theory
Shortest paths, spanning trees and flows on one graph, drawn as they are computed: Dijkstra's ripple, Kruskal's islands, Edmonds–Karp's paths and the cut that equals the flow.
What happens
Forty glowing nodes scattered at random, each joined to its four nearest and to whatever else it takes to make one connected piece - a hundred edges, their lengths the weights and a capacity from one to nine each. Three questions, each answered in front of you a step at a time. Shortest paths: Dijkstra settles nodes in order of distance from the source S, and the settled set grows out of S like a ripple - a node is finished the moment its distance can no longer improve - until the sink T is reached and its path lights up with the distances along it. Bellman–Ford, a method with no priority queue at all, agrees node for node, and the triangle inequality holds on every edge. Spanning tree: Kruskal takes the edges lightest first, keeps one that joins two islands (green), drops one that would close a loop (red), and the tree is complete at N − 1 edges; every skipped edge is the heaviest on the loop it would have closed, which is why the greedy choice is the cheapest wiring. Flow: Edmonds–Karp finds the shortest path with spare capacity from S to T, pushes the bottleneck along it, and repeats, the edges filling toward their capacities, until no path is left - and then the cut lights up between what S can still reach and the rest, and its capacity equals the flow: max-flow = min-cut. Click a node to make it the source, right-click for the sink, drag a node and every answer is recomputed for the new lengths.
Equations used in the module
Equations graph: N points in [−1, 1]² from the shared die (seed 3, N = 40); each joined to its k = 4 nearest, plus the Euclidean minimum spanning tree so the graph is connected; 100 edges, weight = length, capacity 1 … 9 from the same die; S = leftmost node (29), T = rightmost (39) Dijkstra: d(S) = 0, others ∞; settle the unsettled node of least d, relax d(v) = min(d(v), d(u) + w(u, v)) for its neighbours; settled nodes never improve; d(T) = 2.0906 over 6 edges; Bellman–Ford (N − 1 rounds over all edges) agrees to 10^−12; d(v) ≤ d(u) + w(u, v) on every edge Kruskal: edges by weight, keep e when its ends lie in different components (union–find); N − 1 = 39 kept, 61 skipped, weight 8.4480; first skipped edge is the 12th considered; cycle property: a skipped edge is at least as heavy as every edge on the tree path between its ends - so the greedy tree is minimal Edmonds–Karp: residual capacity c(u, v) − f(u, v); breadth-first search from S to T over edges with residual capacity, push the bottleneck b along it, f(u, v) += b, f(v, u) −= b; repeat until no path; 13 paths with bottlenecks 2 1 2 1 1 1 1 1 2 1 1 1 1, flow 16; the cut (nodes S still reaches | the rest) has capacity 16, 35 nodes on the source side; conservation: net flow 0 at every node but S and T simple graph: no loops, no parallel edges; Σ deg(v) = 2E; Euler circuit iff connected and every degree even, Euler path iff exactly two degrees are odd; on c components Kruskal keeps N − c edges
