디닉 알고리즘

네트워크 유량 문제를 해결하기 위해서는 에드몬드 카프 알고리즘을 공부했다. BFS를 이용해 문제를 해결핬다. 하지만 에드몬드 카프 알고리즘의 시간복답도는 O(V*E^2)이다. 이럴 경우 간선이 많아지면 문제 해결 시간이 오래걸린다는 단점이 있다. 그래서 디닉 알고리즘이라는 시간 복잡도가 O(V^2*E)의 알고리즘이 있다. 오늘은 이 알고리즘을 공부해 볼려고 한다.

디닉 알고리즘(Dinic’s Algorithm) 설명

위 그래프는 동아리 시간에 배운 그래프이다. 디닉 알고리즘을 수행 하기 위해서는 먼저 레벨 그래프 부터 만들어야 한다.

 

레벨 그래프

  시작 정점은 언제나 0이고  그와 인접한 정점은 1 또 인접한 정점은 2 로 만     들어진다. 

• 해당 정점은 아직 레벨을 부여 받지 않은 정점이어야 한다.
• 현재에서 다음으로 유량이 흐를 수 있어야 한다.

차단 유량

위 그림 처럼 레벨 그래프가 만들어진다. 파란색 간선이 차단 유량이라고 한다.

위 그래프는 유량을 흘러보낸 것이다. 이럴 경우 유량의 총합은 14이다.

 

반대 방향 유량

에드몬드 카프 알고리즘에서 그랬듯이 유량이 생기면 그에 반대 방향으로 흐르는 유량이 생긴다. 이 상태에서 다시 유량이 흐르면

이 상태로 유량이 흐를 수 있다. 5의 유량이 더 흐를 수 있는 것을 발견 했으므로 총 19의 유량이 흐른다.

모든 정점이 연결 할 수 없을 때 끝난다. 이 알고리즘의 시간 복잡도는 O(V^2E)이다. 즉 간선이 많을 때도 사용 할 수 있다.