LP&CO 2026 Lecture-30
Nishad-Kothari-IIT-Madras · 62:00
The lecture works through the primal-dual algorithm for the shortest s–t path problem on a worked example, then shows why it is correct. The algorithm keeps dual labels on s–t cuts and repeatedly raises the label of t...