네트워크 유량, Dinic 알고리즘

[1. 개요]

네트워크의 최대 유량을 계산 할 때, 포드-풀커슨 알고리즘 외 디닉 알고리즘에 대한 정리

• https://testkernelv2.tistory.com/601

---

[2. 알고리즘]

디닉 알고리즘은 두가지 단계로 구성 된다.

1. Level graph 의 생성
2. Blocking flow 를 지키면서, 유량을 흘려보냄.

더 이상 source 에서 sink 로 유량을 흘려 보낼 수 없을 때까지 위 과정을 반복한다.

• 증가 경로 (Augmenting path) 가 없을 때 까지

---

[3. Level graph]

레벨 그래프는 BFS 를 이용하여 계산한다.

Source 에서 시작하여, Sink 에 도달 할 때 까지 BFS 를 진행 하는 것이다.

 

여기서 Level 은 각 노드에 설정 되는데, Source 에서 해당 노드까지 도달한 최소 hop 이라고 생각하면 된다.

• edge 의 weight 가 없는 경우(혹은 weight 가 모두 같은 경우), bfs 는 최단 경로를 계산 한다.

단, 한가지 중요한 점은 a -> b 로 이동 시 잔여 용량이 있어야 한다는 것 이다.

• 알고리즘이 1~2 과정을 반복하므로, 현재 네트워크에서 잔여 용량은 최초와 다를 수 있다.

---

[4. Blocking flow]

차단 유량은 레벨 그래프가 계산 된 뒤, source 에서 sink 로 실제 유량을 흘려 보내는 것이다.

여기서 중요한 점은 몇 가지가 있는데,

1. 경로 상 인접한 노드의 level 은 정확히 1 차이가 나야하고,
2. edge 의 잔여 용량이 있어야 하며,
3. source -> sink 로 가는 모든 경로에 대해서 진행 해야 한다는 것이다.

경로는 여러개 가 될 수 있으므로, 하나의 경로 생성 후, 해당 경로 상 잔여 용량을 반드시 갱신해주어야 한다.

---

[5. 구현]

관련 예제의 코드로 대체 한다.

• https://testkernelv2.tistory.com/721