최대 유량을 찾는 에드몬드 카프 알고리즘(Edmonds-Karp Algorithm) 배우기

1. 유량 네트워크(flow network)

 

A에서 B까지 8명이 지나갈 수 있고, B에서 C까지 3명이 지나갈 수 있다고 해보자.

 

A에서 C까지 1초가 걸린다고 한다면, A에서 B로 8명을 보낼때, 1초 후에 상황은 어떻게 될까

 

그러면 B에 5명이 대기하고 있고, C에는 3명이 도착해있다.

 

 

즉, A에서 B로 8명씩 보내는건 손해라는 의미

 

A에서 B로 8명씩 보낼 수 있지만, A에서 C까지 막힘없이 데이터를 전송할려면 1초에 3명씩 보내야한다는 소리이다.

 

위의 그림은 A에서 B로 최대 8명이 갈 수 있는데, 실제로는 3명이 흐르고 있다는 뜻

 

때때로 네트워크상 특정 지점에서 다른 지점으로 실제로 데이터가 얼마나 흐르고 있는가를 측정하는 것에 관심이 있다.

 

송유관에서 두 도시 사이 보낼 수 있는 석유의 양, 도로에서 두 도시 사이 교통 체증, 네트워크 상 데이터 전송 등 현실에서 활용 분야가 많다.

 

이러한 상황에서 관심 있는 문제는 어떤 지점에서 다른 지점으로 막힘 없이 보낼 수 있는 가장 많은 유량은 얼마인가?

 

 

2. 정의

 

1) 유량 네트워크(flow network)

 

각 간선(edge)이 음이 아닌 용량(capacity)을 가지는 방향 그래프(directed graph)

 

만약 두 정점 u와 v사이 간선이 없다면 용량 c = 0이다.

 

2) source

 

유량의 시작 지점

 

 

3) sink

 

유량의 도착 지점

 

 

4) 용량(capacity)

 

각 간선에서 흐를 수 있는 최대 유량(flow)

 

 

5) 유량(flow)

 

각 간선에서 실제로 흐르는 데이터의 양

 

 

6) 용량 한계(capacity constraint)

 

모든 정점 u,v에 대하여 u에서 v로의 유량 f(u,v)는 u에서 v로의 용량 c(u,v)을 넘을 수 없다.

 

즉, $f(u,v) \leq c(u,v)$

 

7) 유량 대칭성(skew symmetry)

 

모든 정점 u,v에 대하여 u에서 v로 들어가는 유량은 v에서 u로 나가는 음수 유량과 같아야한다.

 

즉, $f(u,v) = -f(v,u)$

 

 

8) 유량의 보존(flow conservation)

 

source와 sink를 제외한 모든 정점 u에 대하여, 다른 모든 정점 v로 가는 유량의 합은 0이다.

 

즉, $\sum_{v \in V} f(u,v) = 0$

 

어떤 정점 u로 들어오는 유량만큼 다른 정점으로 유량이 나가야한다는 소리

 

 

9) net flow

 

source에서 sink로 가는 유량의 크기는 source에서 다른 모든 정점 v로 가는 유량의 합과 같다.

 

$|f| = \sum_{v \in V} f(s,v)$

 

여기서 s는 source이다.

 

이것의 최댓값을 구하는 문제가 최대 유량 문제(maximum flow problem)

 

 

3. 최대 유량 문제(maximum flow problem)

 

다음과 같은 그래프에서 A에서 D로 막힘없이 흐르도록 하는 최대한 많은 유량을 보내고자 할때, 얼마일까?

 

 

당연히 5이다. 5보다 큰 유량을 보내면, C에서 D 사이에 정체 현상이 일어날 수 있다.

 

이처럼 경로상에서 가장 작은 용량만큼 보내는 유량이 해당 경로에서 흐를 수 있는 최대 유량이라는 것을 알 수 있다.

 

조금 더 복잡한 그래프를 보자.

 

다음 그래프에서 빨간 선으로 이동한다면, 가장 작은 용량인 10만큼의 유량을 보낼 수 있다.

 

 

 

 

하지만 유량을 최대한 보내고 싶다면, 여러 경로로 나눠서 유량을 최대한 보내는게 유리하다

 

각 간선마다 가지는 용량을 최대한 활용해서, 여러 경로로 다음과 같이 나눠보낸다면...

 

 

s에서 t까지 최대 17의 유량을 보낼 수 있다.

 

 

4. 포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)

 

유량 네트워크에서 하나의 경로로 유량을 보냈을때, 어떤 경로로 유량을 더 보내야 많은 유량을 보낼 수 있을까?

 

하나의 경로로 유량을 보내면, 각 간선에서 용량과 유량의 차이만큼 유량을 더 보낼 수 있는데 이를 residual network라고 부른다

 

이 residual network에서 어떤 경로로 유량을 보낼 경우 전체 유량이 증가한다면,

 

그러한 경로로 유량을 보내면 전체 유량이 증가하니, 그런 경로를 어떻게든 모두 찾고자 하는 알고리즘이다.

 

 

어떻게 찾는지는 구체적으로 명시하지는 않았다고 한다

 

그래프에서 경로를 찾는 알고리즘은 DFS와 BFS가 있기 때문에, 둘 중 하나로 '전체 유량이 증가하는 경로'를 모두 찾는다

 

 

하지만 찾는 방법에 약간의 테크닉이 필요한데, 다음과 같은 그래프를 보자.

 

 

 

S에서 T로 유량을 보낼때, S > A > T로 보낼 경우 1만큼 보낼 수 있다.

 

 

 

그러면 S > A는 0만큼 보낼 수 있고 A > T로는 2만큼 보낼 수 있는데.. 이렇게 만들어진 network가 residual network이다.

 

여기서 유량을 더 증가시키는 경로를 찾아야하는데 S > B > T로 1만큼 더 보낼 수 있게 된다

 

 

 

근데 최초에 다음과 같이 유량을 보낸다면...

 

 

이후로는 유량을 더 보낼 수 있는 경로가 없다

 

이를 해결하기 위해 유량의 상쇄(flow canceling)를 생각했는데,

 

유량의 대칭성에 의해 들어가는 유량만큼 반대방향으로 음의 유량이 빠져나온다고 정의했으므로,

 

각 간선에서 반대방향으로도 유량이 음의 유량으로 빠지고 있다고 생각했다

 

 

 

반대 방향으로 나가는 유량을 생각하기 위해 최초에 네트워크에서 반대방향 간선도 모두 생각을 해놓는다. 

 

유량 네트워크를 정의할때, 두 정점 사이에 간선이 존재하지 않는다면, 그러한 간선의 용량은 0으로 정의했다.

 

그래서 s > a로 가는 간선은 존재하지만, a > s로 가는 간선은 존재하지 않으므로 용량이 0인 간선을 그린다면...

 

 

 

이러한 상태에서 S > A > B > T로 가는 유량의 흐름은...

 

 

여기서 S > A로 1만큼 흐를때, A > S로는 -1만큼 흐른다고 생각을 했는데...

 

용량은 0이지만 유량은 -1이 흐르고 있으니 용량의 한계법칙에 의해 유량 <= 용량이 여전히 성립한다

 

따라서 해당 간선은 여전히 유량이 흐를 수 있다.

 

 

 

이러한 상태에서 S > B > A > T로 유량을 보낼 수 있을까?

 

residual을 생각한다면...

 

S > B로 2, A > T로는 3인데.. B > A로는 흐르는 유량이 -1이고 용량이 0이므로, 용량과 유량의 차이인 1만큼 더 흐를 수 있다.

 

즉 S > B > A > T 경로에서 최소 residual이 1이므로 1만큼의 유량을 보낼 수 있게 된다.

 

 

이 때, 각 간선 a > b로 f만큼 흐른다면 유량의 대칭성으로부터 b > a로는 -f만큼 흐른다고 정의했기 때문에...

 

각 간선에서 반대방향으로 흐르는 음수 유량도 꼭 생각을 해준다.

 

 

이러면 S >A > B > T로 유량을 보내고, S > B > A > T로 유량을 보내는데..

 

A와 B가 서로 유량을 1 주고 -1 받고, 1 주고 -1 받고... 총량이 0이 되기 때문에.. 서로 주고 받는 유량이 0이나 마찬가지다.

 

이를 유량의 상쇄(flow canceling)라고 부른다.

 

이렇게 되면 사실은 S > A > B > T로 유량을 보내고 S > B > A > T로 유량을 보내는 것은..

 

 

놀랍게도 S > A > T로 유량을 보내고 S > B > T로 유량을 보내는것과 마찬가지다..

 

이렇게 하면 최대 유량을 찾을 수 있다고 하는데.. 알고리즘이 정당하다는 것을 보이는 것은 몇단계 레벨이 더 높을 정도로 매우 어렵다..

 

일단 받아들이고 언젠가 공부할 기회가 있겠지

 

이때, 시간복잡도는 최대 유량이 f일때, O(fE)정도로 알려져 있다. 

 

당연히 최대 유량의 크기가 매우 크다면.. 시간이 매우 오래 걸릴 것이다.

 

 

5. 에드몬드 카프 알고리즘(Edmonds-Karp Algorithm)

 

DFS나 BFS를 이용해 유량 네크워크의 모든 '유량이 증가하는 경로'를 찾아서 유량을 보내는 방법으로 최대 유량을 찾을텐데

 

BFS를 사용하면 경로를 많아야 VE번 찾는다는 것이 증명되었다.

 

대략적으로 한번 생각해본다면...

 

BFS를 이용해서 source에서 sink로 가는 고정된 경로의 길이가 D인 어떤 '유량이 증가하는 경로'로 유량을 보내고자 한다.

 

일단 유량을 보내면 해당 경로중 하나의 간선은 반드시 용량이 가득찬다.

 

왜냐하면 최소 용량을 가지는 간선의 용량만큼 유량을 보내기 때문이다.

 

그러면 해당 경로로는 다시는 유량을 보내지 않는다. 왜냐하면 그 경로중 하나의 간선의 잔여 용량이 존재하지 않기 때문이다.

 

이렇게 유량을 보낼 수 있는 길이 D인 경로는 많아야 최대 E개이다.

 

이 과정을 D = 1,2,3,...,V에 대해 반복한다면.. 많아야 최대 VE번 반복하게 된다. 

 

왜냐하면 경로의 길이의 최댓값은 꼭짓점의 수 V를 넘지 않기 때문이다.

 

고정된 정점 S에서 T로 탐색하는 BFS 한번의 시간복잡도는 O(E)이다.

 

그러므로 BFS로 유량을 보내는 에드몬드 카프 알고리즘의 시간복잡도는 $O(VE^{2})$으로 알려져있다.

 

웬만하면 BFS로 경로를 찾는 에드몬드 카프 알고리즘이 효율적이라고 알려져있다.

 

 

6. 연습문제

 

17412번: 도시 왕복하기 1 (acmicpc.net)

17412번: 도시 왕복하기 1

 

7. 풀이

 

1번 정점에서 2번 정점으로 가는 경로를 최대한 많이 찾고 싶은데, '한 경로에 포함된 길이 다른 경로에 포함되면 안된다'

 

주어진 그래프를 용량이 1인 그래프로 만들고, 매 경로에 유량을 1씩 보낸다면.. 유량이 흐르는 해당 경로로는

 

유량을 보낼 수 없기 때문에.. 다른 경로로 유량을 보내야한다.

 

즉, 해당 경로에 포함되지 않는 다른 길로 유량을 보내야한다.

 

그러므로 용량이 1인 그래프에서 1번 정점에서 2번 정점으로 보낼 수 있는 최대 유량이 얼마인지 구하는 문제와 같다.

 

 

기본 세팅은 다음과 같이 한다.

 

1) 그래프, 용량 그래프, 유량 그래프를 모두 정의해야한다.

 

여기서 핵심은 a > b로 가는 간선이 존재하지 않으면 용량은 0으로 정의하기 때문에 용량 그래프의 초기값은 0이다.

 

또한 a > b로 가는 간선만 존재한다고.. 그래프에서 a > b로 가는 간선만 추가하면 안된다.

 

반대 방향으로 흐르는 유량도 생각해야하므로 최초 유량 네트워크를 구성할때는 반대 방향 간선도 추가해놓는다.

 

n,p = map(int,stdin.readline().split())

graph = [[] for _ in range(n+1)] #유량 네트워크

#a > b로 가는 간선이 존재하지 않으면, 용량은 0으로 정의하기 때문에 초기값을 0으로
capacity = [[0]*(n+1) for _ in range(n+1)] #각 간선의 용량

flow = [[0]*(n+1) for _ in range(n+1)] #각 간선에서 흐르는 유량

for _ in range(p):
    
    a,b = map(int,stdin.readline().split())
    
    graph[a].append(b)
    graph[b].append(a) #반대 방향으로 흐르는 유량을 생각해야하므로,
    capacity[a][b] = 1 #a > b로 가는 간선이 존재하는 경우 용량은 1로 제한

source = 1 #유량의 시작점
sink = 2 #유량의 도착점

print(edmonds_karp(source,sink))

 

2) 이제 source에서 sink로 가는 유량이 증가하는 모든 경로를 BFS로 찾는다.

 

일반적인 BFS처럼 deque를 사용해서 시작점 s부터 시작하고... 방문 지점을 경로를 담은 path배열로 체크해주자.

 

이때, s에서 v로 가는 방문 조건은 잔여 용량 residual이 0보다 커야 유량이 흐를 수 있고,

 

아직 v를 방문하지 않아야한다.

 

잔여 용량 residual = s에서 v로 가는 용량 - s에서 v로 현재 흐르는 유량 = capacity[s][v] - flow[s][v]

 

만약, BFS중 sink인 t에 도달했다면.. 현재 흐르고 있는 유량을 체크해준다.

 

만약, 더 이상 유량을 보낼 수 없다면 큐가 빌것인데, 그 경우 0을 return해서 더 이상 경로를 찾을 수 없다고 알려준다.

 

#s에서 t로 가는 '유량이 증가하는 경로'를 찾는 bfs
def bfs(s,t):
    
    queue = deque([s])

    path = [0]*(n+1)

    while queue:
        
        u = queue.popleft()

        for v in graph[u]:
            
            #u에서 v로 용량이 남아(residual) 갈 수 있고 아직 방문하지 않았다면...
            if capacity[u][v] - flow[u][v] > 0 and path[v] == 0:

                queue.append(v)
                path[v] = u #v의 이전 정점이 path[v]

                if v == t: #도착점 sink에 도달했다면....

                    return make_flow(s,t,path) #유량 그래프에 현재 경로에서 흐르는 유량을 기록

    return 0 #더 이상 경로를 찾지 못한 경우

 

여기서 path 배열로 현재 v에 도달했을때, v에 도달하기 이전 정점을 반드시 체크해줘야하는데..

 

이는 유량을 계산하기 위해서이다.

 

3) BFS로 경로를 탐색했을때, sink에 도달했으면 유량이 얼마나 흐르는지를 계산해준다.

 

이때, 흐를 수 있는 유량은 해당 경로의 간선들의 잔여 용량(residual)들 중 최솟값만큼 유량을 보낼 수 있다는 것을 배웠다.

 

그러므로 경로를 역추적해서 잔여 용량의 최솟값이 얼마인지 구하면 된다.

 

from collections import deque
from sys import stdin

INF = 1000000000000000000000000

#경로 path의 유량을 찾는 함수
#경로 path에서 흐를 수 있는 유량은 각 경로를 구성하는 간선이 가지는 잔여 용량들 중 최솟값
def make_flow(s,t,path):
    
    c = INF #잔여 용량의 최솟값

    #끝점 t부터 시작해서 역으로 돌아가면서
    #경로 path의 흐를 수 있는 최소 용량을 찾는다
    #즉, 경로 path를 구성하는 간선들의 잔여 용량중 최솟값을 찾는다.
    v = t

    while v != s: #경로를 역으로 돌면서 시작점 s에 도달했다면 반복문 탈출
        
        #v의 이전 정점 path[v]에서 v로 가는 경로의 잔여 용량이 c보다 작다면,
        #c를 해당 값으로 갱신
        if (capacity[path[v]][v] - flow[path[v]][v]) < c:
            
            c = capacity[path[v]][v] - flow[path[v]][v]

        v = path[v] #v의 이전 정점이 path[v]
    
    #해당 경로에서 흐르는 유량을 찾았으면, 경로를 역추적
    #해당 경로를 구성하는 간선들에 유량을 더해주자
    v = t

    while v != s:
        
        #이전 정점 path[v]에서 v로 가는 유량에 c를 더해주고..
        flow[path[v]][v] += c 

        #유량 대칭성
        #path[v]에서 v로 들어가는 유량과 v에서 path[v]로 나가는 유량이 같다
        flow[v][path[v]] -= c
        v = path[v]
    
    return c

 

4) 경로를 역추적해서 잔여 용량들의 최솟값을 찾았으면, 유량 그래프를 갱신해주자.

 

다시 path 배열을 역추적해서, 해당 유량들을 더해주면 된다.

 

여기서 중요한 점은 a > b로 유량 f가 흐르면, b > a로 -f가 흐르도록 만들어줘야한다는 점이다.

 

그래야 유량의 상쇄(flow canceling)가 일어나기 때문이다.

 

 

5) 이제 source에서 sink로 가는 유량이 존재하지 않을때까지 BFS로 계속 탐색하면 된다.

 

BFS 값이 0을 return하면 반복문을 끝내면 된다.

 

def edmonds_karp(s,t):
    
    path = 0
    
    #s에서 t로 가는 유량이 존재하는지 찾을 수 없을때까지 BFS로 찾는다
    while 1:
        
        c = bfs(s,t)

        if c > 0: #s에서 t로 가는 유량이 존재한다 = 경로가 존재한다 
            
            path += 1
        
        else: #더 이상 흐를 수 있는 유량이 없다 = 경로가 존재하지 않는다
            
            break
    
    return path

 

 

참고

 

https://iknoom.tistory.com/13

최대 유량 알고리즘(maximum flow algorithm)

 

https://www.youtube.com/watch?v=BQ0Yq-sufnk 

 

 

https://www.youtube.com/watch?v=Wn51_ypG_T8 

 

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap27.htm

Intro to Algorithms: CHAPTER 27: MAXIMUM FLOW

 

 

https://koosaga.com/18

유량 관련 알고리즘 정리

 

https://koosaga.com/133

유량 관련 알고리즘 증명

 

https://velog.io/@kasterra/%EC%9C%A0%EB%9F%89-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%97%90%EB%93%9C%EB%AA%AC%EB%93%9C-%EC%B9%B4%ED%94%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

유량 그래프 ② : 에드몬드-카프 알고리즘

 

https://cp-algorithms.com/graph/edmonds_karp.html

Maximum flow - Ford-Fulkerson and Edmonds-Karp - Algorithms for Competitive Programming