지난 글에 이어서 더 빠른 최대 유량 알고리즘인 디닉 알고리즘.
에드몬즈-카프는 bfs를 활용하며 O(VE2) 안에 문제를 해결할 수 있다. 간선에 대한 지수시간이기 때문에 정점의 수와 무관하게 간선이 여러 개라면 bfs에서 너무 많은 시간을 소모하게 된다. 하지만 디닉은 정점에 대한 지수시간 O(V2E) 안에 문제를 해결한다.
디닉 알고리즘의 순서는 이렇다.
유량 그래프 = G, source = s, sink = t
1. G의 레벨그래프 L을 만든다.
a. s로부터 t까지의 bfs로 깊이는 각 정점의 레벨이 된다.
b. t의 레벨이 정의되지 않으면 모든 작업을 멈춘다.
2. L에서 다음 작업을 반복한다.
a. dfs로 s→t의 증가경로를 찾는다.
b. 증가경로의 최소 컷을 찾아 경로에 유량을 생성한다.
3. 1.로 돌아가 L을 갱신한다.
지난 번과 같은 방법으로 유량을 표시했다. source는 A, sink는 B다. 먼저 디닉 알고리즘에서는 레벨그래프를 만들어야 한다.
레벨그래프에서는 같은 레벨끼리 간선을 갖지 않는다. 이 레벨그래프에서 증가경로를 찾아보자.
먼저 s→B→C→t를 찾았다. 최소 컷은 B에서 C구간의 3이므로 경로에 3의 유량을 생성한다. 그리고 s→B→E→t를 찾았다. 최소 컷은 s에서 B구간의 2이므로 경로에 2의 유량을 생성한다. 마지막으로 s→D→E→t를 찾았다. 최소 컷은 E에서 t구간의 1이므로 경로에 1의 유량을 생성한다.
이렇게 6의 유량이 생성되었고, 레벨그래프 내에는 더 이상 증가경로를 찾을 수 없다. 이렇게 되면 레벨그래프를 다시 그려봐야 한다.
레벨그래프를 만들 때에는 이미 생성된 유량에 대한 음의 유량도 고려한다. 따라서 B의 레벨은 3이 된다.
증가경로 s→D→E→C→t를 찾았다. 최소 컷은 s에서 D구간의 1이므로 경로에 1의 유량을 생성한다.
더 이상 증가경로가 없으므로 레벨그래프를 다시 만들어본다.
레벨그래프에서 t의 레벨이 정의되지 않았다. 이 경우 더 이상 s에서 t로 이어지는 증가경로가 없는 것이므로 t에 도달한 유량 7이 최대 유량이 된다.
bfs와 dfs가 모두 쓰이는 알고리즘이다. 그리고 레벨그래프에서 dfs를 실행할 때, 매 번 가능성이 없는 간선을 탐색하는 것이 시간소모가 크기 때문에 이전에 탐색한 마지막 간선 정보를 기억해두고 다음 dfs에서는 다음 간선부터 탐색하는 것이 좋다. 물론 레벨그래프가 갱신되었다면 탐색 기록도 초기화 해야 한다.
