Single-Source Shortest Path (SSSP)

overview

Summary

Single-source shortest path (SSSP) finds the minimum-cost path from one start node to every other node in a weighted graph. The right algorithm depends on edge weights and graph structure: BFS for unweighted, Dijkstra for non-negative weights, and Bellman-Ford when negatives exist. Core ideas include relaxation, priority queues, and detecting negative cycles. SSSP powers routing, maps, network optimization, and many scheduling problems.