Single-Source Shortest Paths: Bellman-Ford and DAG Relaxation

BFS finds shortest paths by edge count on unweighted graphs; this note generalises to weighted edges, where the cost of a path is the sum of its edge weights, not just the number of hops. The unifying technique is relaxation: maintain an upper-bound estimate on each vertex's shortest distance, and repeatedly tighten it whenever a cheaper path is discovered. This note builds the relaxation template, then two specialisations: Bellman-Ford, which handles negative edge weights and detects when no shortest path even exists (a negative-weight cycle), and the much faster DAG algorithm, which reuses topological sort directly.