LP&CO 2026 Lecture-29: A primal-dual algorithm for the shortest path problem using the tight digraph
Nishad-Kothari-IIT-Madras · 56:57 · Watch on YouTube
This lecture works through a primal-dual algorithm for the shortest s–t path problem on an example and shows that the basic version can fail. Dual values are raised on s–t cuts until a path of "tight" edges connects s...