LP&CO 2026 Lecture-29
Nishad-Kothari-IIT-Madras · 56:57 · Watch on YouTube
이 강의는 최단 s–t 경로 문제에 대한 쌍대 알고리즘을 예제를 통해 다루며, 기본 버전이 실패할 수 있음을 보여줍니다. 듀얼 값은 s–t 컷에서 상승하여 "타이트한" 엣지의 경로가 s와 t를 연결할 때까지 올라갑니다. 이 경로는 첫 번째 여여 조건(CS) 조건을 만족하지만 양수 값의 컷을 여러 번 교차할 수 있으므로 최단 경로임이 보장되지 않습니다. 강사는 그 다음 해결책을 시작합니다...