Network Flow 알고리즘

이 글에서는 Network Flow 알고리즘 중 다음 세 가지 알고리즘을 간략하게 설명한다.

• Ford-Fulkerson 알고리즘
• Edmonds-Karp 알고리즘
• Dinic 알고리즘

더 강력한 Push-Relabel 알고리즘도 존재하지만 여기서는 다루지 않는다.

 

Ford-Fulkerson 알고리즘

가장 기본적인 알고리즘이다. 동작 과정은 다음과 같다.

잔여 그래프에서 소스에서 싱크로 가는 증가 경로가 존재하면 해당 경로에 유량을 최대로 흘린다.

이를 증가 경로가 존재하지 않을 때까지 반복한다.

알고리즘의 정당성은 Max-Flow Min-Cut theorem을 이용하여 증명할 수 있다.

 

증가 경로를 찾고 유량을 흘리는 부분은 DFS 또는 BFS로 처리할 수 있다.

최대 유량을 f라고 하면 반복 횟수는 최대 f번이다.

따라서 시간 복잡도는 O(Ef)이다.

 

Edmonds-Karp 알고리즘

Ford-Fulkerson 알고리즘에서 BFS를 사용하면 Edmonds-Karp 알고리즘이 된다.

증가 경로를 찾을 때 BFS를 사용하면 해당 경로는 최단 경로가 된다.

 

최단 경로의 길이가 유지될 때 유량을 흘릴 때마다 적어도 하나의 간선이 포화된다.

역간선이 발생하지만 역간선을 거치면 경로의 길이가 길어진다.

따라서 최단 경로의 길이가 유지될 때 해당 간선과 역간선 모두 더 이상 고려하지 않아도 된다.

 

최단 경로의 길이는 V 미만이고 각 길이마다 반복 횟수는 최대 E번이다.

따라서 시간 복잡도는 O(VE^2)이다.

 

Dinic 알고리즘

Dinic 알고리즘의 기본 아이디어는 Edmonds-Karp 알고리즘과 유사하다.

우선 최단 경로를 이루는 간선들로만 구성된 레벨 그래프를 구성한다.

그리고 레벨 그래프에 유량을 최대로 흘린다.

이를 싱크에 도달할 수 없을 때까지 반복한다.

 

레벨 그래프에 유량을 흘릴 때의 시간 복잡도를 생각해보자.

각 유량은 DFS로 O(E)에 흘릴 수 있고 반복 횟수는 최대 E번이다.

따라서 시간 복잡도는 O(E^2)이다.

 

레벨 그래프에서 불필요한 간선은 더 이상 고려하지 않아도 된다.

따라서 불필요한 간선을 삭제하여 시간 복잡도를 개선할 수 있다.

이 경우 DFS의 시간 복잡도는 O(V+k)가 된다. 여기서 k는 삭제한 간선의 수를 의미한다.

따라서 시간 복잡도를 O(VE)로 개선할 수 있다.

 

레벨 그래프는 BFS로 O(E)에 구성할 수 있고 유량은 DFS로 O(VE)에 흘릴 수 있다.

새로운 레벨 그래프에 유량을 흘릴 때마다 최단 경로의 길이는 증가하므로 반복 횟수는 V번 미만이다.

따라서 시간 복잡도는 O(V^2E)이다.

 

Dinic 알고리즘의 소스 코드는 링크에서 확인할 수 있다.

 

연습 문제

1. Maze Movement

gcd

2. RA Duty Scheduler

brute force

3. Jupiter Orbiter

(Q + 1) * N + 2

 

끝

끝