Overview

Topic 4 traversed graphs with unweighted edges; this topic adds edge weights and asks the two questions that dominate real network optimisation: what is the cheapest path between two points, and what is the cheapest way to connect every point at all? Both questions are answered by a single unifying template — the relax-and-check pattern for shortest paths — specialised three ways: Bellman-Ford (handles negative weights, and detects negative cycles), the DAG special case (linear time, reusing topological sort directly), and Dijkstra's algorithm (fastest, but requires non-negative weights). All-pairs shortest paths extends this to every pair simultaneously via Floyd-Warshall's matrix-DP recurrence and Johnson's reweighting trick. Minimum spanning trees (Kruskal, Prim) solve the connectivity-optimisation twin of the shortest-path problem, built on the cut property and cycle property, and Kruskal's implementation motivates Union-Find, a genuinely new data structure whose amortized analysis (the derivation sub-note) is the sharpest amortized bound in the entire unit.