Algorithm Ford-Fulkerson and Edmonds-Karp algorithm

알고리듬 Ford-Fulkerson and Edmonds-Karp algorithm을 알아보겠습니다.

포드 풀커슨 알고리듬과 에드몬드 카프 알고리듬은 최대 유량을 구할 때 사용하는 알고리듬입니다.
​
​
아래와 같은 배관이 구성되어 있습니다.

0에서 4로 흐를 때, 최대로 많이 4로 흘러들어가는 값은 몇일까요?

​

​

이러한 문제를 풀기 위해서 고안된 게 포드 풀커슨 알고리듬입니다.

​

이 알고리듬이 작동하기 위해서는 아래의 4 가지를 가정하고 진행합니다.

1. 허용량 이상으로 흐를 수 없다.

    (0 -> 1은  3을 초과해서 흐를 수 없다.)

2. u에서 v로 흐르는 값은 v에서 u로 음수로 흐른다고 표현할 수 있다.

    (0 -> 2로 2가 흐르면, 2 -> 0로 -2가 흐른다고 표현할 수 있다.)

3. u가 시작점과 끝점이 아니라면, 들어온 만큼 소비를 한다.

    (0->2로 2 만큼 들어갔다면, 2에서 나가는 모든 방향의 흐름의 양은 2가 되어야 한다.)

4. 시작점에서 나온 흐름은 끝점으로 모두 들어가야 한다.

    (0에서 5가 나온다면, 4에 5가 들어가야 한다.)

​

​

이 알고리듬의 핵심은 다음과 같습니다.

1. 모든 흐름을 0으로 만듭니다.

2. 시작점에서 끝점으로 가는 길을 찾습니다. 이때 길은 남은 용량이 0 보다 커야 합니다.

2-1. 찾은 길에서 가장 적은 용량을 찾습니다.

2-2. 찾은 길에 2-1에서 찾은 값을 흘려 더합니다.

​

위의 2 번의 과정에서 DFS(Depth-frist search, 깊이 우선 탐색)과 BFS(Breadth-first search, 너비 우선 탐색)으로 찾을 수 있는데, BFS로 길을 찾으면 에드몬드 카프 알고리듬이라고 합니다.

​

포드 풀커슨의 경우 O(Ef)가 되고, 에드몬드 카프 알고리듬의 경우 O(VE^2)이 됩니다. 따라서 웬만하면 에드몬드 카프 알고리듬을 사용하면 됩니다.

​

여기서는 애드몬드 카프 알고리듬의 코드를 봅시다.

​

​

먼저 클래스를 하나 만듭니다.

저는 FordFulkerson이라는 클래스로 만들었습니다.

__init__(self)에는 graph와 row를 초기화합니다.

graph는 위에 있는 그림을 배열로 만듭니다.

0 번에서는 1 번과 2 번으로 감으로 1과 2 위치에 각 각의 허용치를 적어줍니다. [0, 3, 2, 0, 0]

이런 식으로 4 번까지 적어줍니다.

9 번째 줄에서 prev_node를 만듭니다. 각 노드들이 어디서 왔는지를 알아야 하기 때문이죠.

visited를 만들어서 중복 방문하지 않게 만들 겁니다.

10 번째 줄에서 max_flow를 만들고 여기에 차곡차곡 최대 흐름을 추가할 겁니다.

이제, 이 알고리듬에서 중요한 길 찾기를 해야 합니다.

source에서부터 sink까지 이르는 길입니다.

Queue를 만들어서 BFS(Breadth-first search. 너비 우선 탐색)로 진행할 겁니다.

즉, Edmonds-karp 알고리듬을 사용한다는 말입니다.

​

1 번째 줄처럼 Queue를 import 합니다.

bfs를 정의합니다.

중복 방문하면 안 되기 때문에 visited를 만듭니다.

그리고 12 번째 줄에서 search_queue를 만들고, 14 번째 줄에서 시작점인 source를 큐에 넣고, 15 번째 줄에서 visited의 source 인덱스에 True를 넣습니다.

이제, 탐색을 해봅시다.

​

17 번째 줄에서 queue가 빌 때까지 무한 반복을 시킵니다.

18 번째 줄처럼 queue에서 탐색한 노드 하나를 꺼냅니다.

20 번째 줄처럼 해당 노드의 graph 정보를 가져옵니다. enumerate를 사용하여 index와 value를 동시에 가져옵니다.

만약에 그래프 정보(연결되는 노드와 허용량)가 0이 아니고, 방문한 곳이 아니어야 탐색을 계속 진행합니다.

22 번째 줄에서 다음 탐색할 노드를 search_queue에 넣습니다. 그리고 prev_node 정보를 지금 노드로 업데이트합니다. 다음에 방문할 노드는 지금 노드에서 온 것이기 때문이죠.

24 번째 줄처럼 다음 노드는 방문한 것으로 만듭니다. 이미 큐에 들어갔기 때문에 괜찮습니다.

while 문이 다 끝나면, 검색이 끝났습니다.

sink로 가는 길이 발견되었다면, visited[sink]의 값은 True가 되어 있을 겁니다.

위에서 만든 bfs를 불러옵니다.

​

sink부터 역순으로 가기 때문에 33 번째 줄에서 tmp_u를 만들어서 sink를 받습니다.

34 번째 줄처럼 current_flow에는 미리 가장 큰 값을 넣어줍니다.

35 번째 줄처럼 tmp_u가 source가 될 때까지 반복을 합니다.

37 번째 줄처럼 prev_node를 sink에서부터 역순으로 source까지 찾아가면서 최소 허용치를 구합니다.

40 번째 줄처럼 여기서 구한 current_flow를 max_flow에 더합니다.

이제, 하나의 경로를 찾았으니 다른 경로를 찾아야 합니다.

그런데, 이 상태로 다시 경로를 찾으면 똑같은 경로가 찾아질 겁니다.

그래서, 추가적으로 해야 하는 것은 경로를 없애는 일입니다. 위에서 설명한 것처럼 A -> B로 2 만큼 흐르는 것은 B -> A 만큼 -2 흐르는 것과 같습니다.

​

​

42 번째 줄처럼 다시 뒤에서부터 역순으로 진행하기 위해 sink를 대입합니다.

흐름 정보가 있는 graph에 정방향은 흐름이 이미 결정되었으므로 현재 흐름만큼 허용치를 뺍니다.

graph에 역방향은 허용치가 늘어나므로 현재 흐름만큼 허용치를 더해줍니다.

지금 상태를 그림으로 살펴보면 다음과 같습니다.

0 -> 2 -> 4로 2 만큼 흐릅니다.

여기서 저 결정된 흐름만큼 허용치를 역으로 해줍니다. 여기서는 2 가 빼집니다.

​

이런 흐름이 됩니다. 그러면, 다음 경로를 탐색할 때에는 0 -> 2로 가는 경로는 없어집니다. 따라서 0 -> 1로 가는 경로로 찾아집니다.

이러한 경우를 반복하면 최대 흐름이 결정됩니다.

50 번째 줄에서 max_flow를 반환합니다.

59 번째 줄처럼 실행해 봅시다.

5가 나옵니다.

끝.

카테고리: Algorithm