slowgrid

최대 유량(4) Push-Relabel은 어떻게 동작하는가

지금까지 최대 유량을 공부하면서 세 가지 알고리즘을 차례로 살펴봤다.포드-풀커슨에서는 Source에서 Sink까지 갈 수 있는 증가 경로(Augmenting Path) 를 찾고, 그 경로로 보낼 수 있는 만큼 유량을 보내는 기본 구조를 살펴봤다.에드몬드-카프에서는 증가 경로를 BFS로 찾도록 선택 규칙을 정하면서, 증가 경로를 어떤 순서로 선택하느냐가 알고리즘의 성능에도 영향을 줄 수 있구나.라는 점을 볼 수 있었다.그리고 Dinic을 정리한 글에서는 여기서 한 단계 더 나아가, BFS로 최단 거리 정보를 한 번 만들었다면, 그 정보를 증가 경로 하나보다 더 많이 활용할 수 없을까?라는 질문을 따라갔다.Dinic은 BFS로 Level Graph를 만들고, 그 구조가 유효한 동안 DFS를 반복해서 가능한 ..