Implemented the Successive Shortest Path algorithm from scratch, including residual graph construction, Bellman–Ford based minimum-cost path extraction, and flow augmentation logic.
Designed and executed large-scale experimental evaluation on randomized Euclidean directed graphs across 28 configurations with varying density (𝑟), capacity bounds, and cost regimes.
Compared SSP, Capacity Scaling, Scaling-SSP, and Primal–Dual algorithms using metrics including total cost, flow value, number of augmenting paths, mean path length, and proportional path length.
Demonstrated that the Primal–Dual algorithm consistently achieves optimal minimum cost, while SSP achieves competitive performance in sparse regimes and degrades in dense graphs.
