Dinic's Algorithm

최종 수정:

1레벨 그래프와 차단 유량

방향 그래프 G = (V, E), 소스 s, 싱크 t, 용량 함수 c: V × V → ℝ≥0 (E 밖의 쌍은 0), n = |V|, m = |E|이 주어진다. 잔여 용량 r(u,v) = c(u,v) − f(u,v), 잔여 그래프 Gf = (V, Ef), Ef = { (u,v) : r(u,v) > 0 }이다.

BFS로 Gf에서 s까지의 최단 거리 ℓ(v) = distGf(s, v)를 구한다.

레벨 그래프(level graph): ℓ(v) = ℓ(u) + 1인 간선 (u,v) ∈ Ef만 남긴 부분 그래프 GL.

차단 유량(blocking flow): GL의 모든 s-t 경로에 포화된 간선이 존재하는 유량 B.

2알고리즘

Gf에 s → t 경로가 없을 때까지 다음을 반복한다.

  1. BFS로 Gf의 레벨 그래프 GL을 구성한다.
  2. GL에서 차단 유량 B를 구한다.
  3. f ← f + B.

종료 시 Gf에 s → t 경로가 없으므로, Max-Flow Min-Cut Theorem에 의해 f는 최대 유량이다.

3시간 복잡도

3.1보조 정리 1

각 반복 직후, B를 보낸 후의 잔여 그래프 Gf'에 대해 distGf'(s, t) > distGf(s, t)이다.

우선 Gf'의 임의의 간선 (u, v)에 대해 ℓ(v) ≤ ℓ(u) + 1임을 보인다.

  • Gf에 있던 간선: 최단 거리 부등식에 의해 ℓ(v) ≤ ℓ(u) + 1.
  • B가 새로 만든 역방향 간선 (u, v): B가 레벨 그래프 간선 (v, u)를 사용했으므로 ℓ(u) = ℓ(v) + 1, 즉 ℓ(v) = ℓ(u) − 1 ≤ ℓ(u) + 1.

d = ℓ(t) = distGf(s, t)로 두자. Gf'에 길이 l ≤ d인 s-t 경로 P = s = u0 → u1 → ⋯ → ul = t가 존재한다고 가정한다. ℓ(s) = 0, ℓ(t) = d이고 각 간선이 ℓ을 최대 1 증가시키므로, l = d이고 각 간선 (uk−1, uk)에서 ℓ(uk) = ℓ(uk−1) + 1이어야 한다. 역방향 간선은 ℓ을 1 감소시키므로 P에 쓰일 수 없다. 따라서 P의 모든 간선은 Gf에 존재하고 ℓ(uk) = ℓ(uk−1) + 1인 레벨 그래프 간선이므로, P는 GL의 s-t 경로다. 차단 유량의 정의에 의해 P에는 B로 포화된 간선이 존재하는데, 포화된 간선은 Gf'에 없으므로 P ⊆ E(Gf')에 모순이다. ■

따름 정리: 단계 수는 최대 n − 1이다.

3.2시간 복잡도

보조 정리 1에 의해 단계 수 O(n), 각 단계에서 BFS O(m) + 차단 유량 O(nm)이므로 전체 시간 복잡도는 O(n2m)이다.

Link-Cut Tree를 이용하면 차단 유량을 O(m log n)에 구할 수 있어 전체 복잡도가 O(nm log n)이 된다.

4참고 문헌

  • Dinic, E. A. (1970). Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Mathematics Doklady, 11, 1277–1280.
  • Even, S., & Tarjan, R. E. (1975). Network flow and testing graph connectivity. SIAM Journal on Computing, 4(4), 507–518.