139. Ford-Fulkerson Algorithm

포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)은 일반적인 방향 그래프에서 최대 유량을 구하는 가장 간단한 알고리즘이다. 최대 유량은 일반적으로 소스에서 간선들을 따라서 싱크로 흘려보낼 수 있는 유량의 최댓값을 의미한다. 이 알고리즘은 다음과 같은 방법으로 작동한다.

 

    1. 모든 간선의 유량을 $0$으로 초기화한다.

    2. 소스에서 싱크로 데이터를 보낼 수 있는 경로를 찾는다. 이 경로를 증가 경로(Augmenting Path)라고 한다.

    3. 증가 경로 중 더 보낼 수 있는 데이터의 양이 가장 작은 간선을 찾는다. 이 간선에 더 보낼 수 있는 데이터의 양을 $w$라고 하자.

    4. 찾은 증가 경로를 통해 $w$의 데이터를 보낸다. 증가 경로에 포함된 모든 간선의 유량이 $w$만큼 증가하고, 그 간선들에 대응하는 역방향 간선의 유량은 $w$만큼 감소한다.

    5. 위 과정을 반복하다가 그래프에 증가 경로가 없는 경우 실행을 종료한다.

 

아래 그래프를 예시로 들어 살펴보자. 소스가 $\text{S}$, 싱크가 $\text{T}$이다. 각 간선에 표기된 수들은 유량/용량을 나타낸다.

먼저 증가 경로를 아무거나 하나 찾는다. $\text{S}$ - $\text{C}$ - $\text{B}$ - $\text{T}$ 경로가 선택되었다면, 더 흘려보낼 수 있는 유량이 $4$이므로 이 경로로 $4$의 유량을 흘려보낸다.

다시 증가 경로를 찾는다. $\text{S}$ - $\text{A}$ - $\text{B}$ - $\text{T}$ 경로가 선택되었다면, 더 흘려보낼 수 있는 유량이 $4$이므로 이 경로로 $4$의 유량을 흘려보낸다.

이제 이 그래프에는 증가 경로가 없는 것처럼 보인다. 하지만 역방향 간선을 고려하면 상황이 달라진다.

역방향 간선의 유량과 용량은 위와 같다. 그렇다면 이 그래프에는 $\text{S}$ - $\text{A}$ - $\text{B}$ - $\text{C}$ - $\text{D}$ - $\text{T}$라는 증가 경로가 있는 것이 된다. 이 경로로 $1$의 유량을 흘려보낸다.

이제 역방향 간선까지 고려해도 증가 경로를 찾을 수 없다. 따라서 실행을 종료한다. 소스에서 싱크로 흘려보낸 유량은 $9$이다.

 

위 과정에서 역방향 간선으로 유량을 흘려보내는 것은 정방향 간선으로 흘려보낸 유량을 상쇄하는 의미로 이해하면 된다. 어떤 경우는 역방향 간선으로 유량을 흘려보내는 상황이 발생하지 않을 수도 있다.

---

포드-풀커슨 알고리즘은 그래프에서 최대 유량을 쉽게 구할 수 있는 방법이지만, 한 가지 큰 문제점이 있다. 증가 경로를 어떤 방식으로 찾는지가 정의되어 있지 않다는 것이다. 이것이 어떤 그래프에서 이 알고리즘의 성능을 저하시킬 수 있는 요인으로 작용하기 때문에 플로우 문제를 풀 때에는 포드-풀커슨 알고리즘을 잘 사용하지 않게 되었다. 대신 사용할 수 있는 방법이 다음에 소개할 에드몬드-카프 알고리즘이다.