네트워크 플로우 문제 해결: 에드몬드-카프 알고리즘

작성일 : 2024-06-17

네트워크 플로우 문제 해결: 에드몬드-카프 알고리즘

개요

네트워크 플로우 문제는 그래프 이론에서 중요한 문제입니다. 이 문제의 목표는 소스(source) 노드에서 싱크(sink) 노드로 최대 유량(maximum flow)을 찾는 것입니다. 에드몬드-카프 알고리즘은 이러한 문제를 해결하는 데 널리 쓰이는 알고리즘 중 하나로, 폭넓이 우선 탐색(Breadth-First Search, BFS)를 사용하여 잔여 용량(residual capacity)을 찾고 증강 경로를 통해 유량을 최대화합니다.

에드몬드-카프 알고리즘 개념

에드몬드-카프 알고리즘은 기본적으로 포드-풀커슨 알고리즘의 특수한 형태로 볼 수 있습니다. 포드-풀커슨 방법론은 가능한 경로를 통해 최대 유량을 찾는 전략인데, 에드몬드-카프는 이 경로 탐색을 BFS를 사용하여 수행합니다. BFS를 사용함으로써, 이 알고리즘은 시간 복잡도를 크게 줄일 수 있습니다. 해당 알고리즘의 시간 복잡도는 O(Eu^2), 여기서 E는 간선의 수, u는 네트워크의 최대 유량을 나타냅니다.

구현 단계

에드몬드-카프 알고리즘을 구현하기 위한 주요 단계는 다음과 같습니다.

그래프 초기화

각 간선에 대한 유량을 0으로 초기화합니다.
잔여 용량 그래프를 원본 그래프와 동일하게 설정합니다.

증강 경로 탐색

BFS를 사용하여 소스에서 싱크로가는 증강 경로를 찾습니다. 이때, 잔여 용량이 0보다 큰 간선만 탐색합니다. BFS는 다음과 같은 방식으로 동작합니다.

초기 상태에서 소스를 큐에 넣습니다.
큐에서 노드를 하나 꺼내어 인접한 노드를 검사합니다. 인접한 노드의 잔여 용량이 0보다 크다면, 해당 노드를 큐에 넣고 경로를 기록합니다.
싱크를 찾을 때까지 이 과정을 반복합니다.


python
from collections import deque

def bfs(residual_capacity, source, sink, parent):
    visited = [False] * len(residual_capacity)
    queue = deque([source])
    visited[source] = True
    
    while queue:
        u = queue.popleft()

        for ind, val in enumerate(residual_capacity[u]):
            if visited[ind] == False and val > 0:
                queue.append(ind)
                visited[ind] = True
                parent[ind] = u

                if ind == sink:
                    return True
    return False

유량 갱신

BFS를 통하여 증강 경로를 찾으면 해당 경로의 최소 잔여 용량을 찾습니다.
찾은 최소 잔여 용량을 사용하여 경로 상의 모든 간선의 유량을 갱신합니다.
유량을 갱신한 후, 거꾸로 흐르는 역경로를 통해 잔여 용량을 업데이트합니다.


python
def edmonds_karp(capacity, source, sink):
    parent = [-1] * len(capacity)
    max_flow = 0
    residual_capacity = [list(row) for row in capacity]

    while bfs(residual_capacity, source, sink, parent):
        path_flow = float('Inf')
        s = sink

        while s != source:
            path_flow = min(path_flow, residual_capacity[parent[s]][s])
            s = parent[s]

        v = sink
        while v != source:
            u = parent[v]
            residual_capacity[u][v] -= path_flow
            residual_capacity[v][u] += path_flow
            v = parent[v]

        max_flow += path_flow

    return max_flow

실제 적용 사례

에드몬드-카프 알고리즘은 실제 네트워크 플로우 문제에서 광범위하게 응용됩니다. 예를 들어, 전형적인 응용 사례는 다음과 같습니다.

교통 흐름 최적화

도시의 도로 네트워크에서 차량의 흐름을 최적화하기 위해 에드몬드-카프 알고리즘을 사용할 수 있습니다. 각 도로의 용량을 설정하고 실제 최대 교통량을 계산하는 방식입니다.

네트워크 용량 관리

컴퓨터 네트워크에서 데이터 흐름을 최적화할 때도 유용합니다. 네트워크 노드와 링크를 그래프로 모델링하고 데이터를 전송할 최대 용량을 계산합니다.

최대 매칭 문제

여러 개의 작업과 여러 개의 작업자를 연결하는 최대 매칭 문제에서 에드몬드-카프 알고리즘을 사용할 수 있습니다. 각 작업과 작업자를 그래프의 노드로, 작업과 작업자 간의 가능성을 간선으로 설정하여 문제를 해결할 수 있습니다.

결론

에드몬드-카프 알고리즘은 네트워크 플로우 문제를 효율적으로 해결할 수 있는 강력한 도구입니다. BFS를 사용하여 증강 경로를 탐색하고 이를 통해 최대 유량을 계산하는 방식은 다양한 실무 응용 사례에 적합합니다. 이 알고리즘을 이해하고 구현하는 것은 네트워크 플로우 문제를 해결하는 데 큰 도움이 될 것입니다.