Ford-Fulkerson & Edmons-Karp 알고리즘

 

 

포드퍼커슨과 에드몬드카프 알고리즘은 네트워크 관련 문제에서 가장 많이 출제되며, 그래프 순회의 고급 기술로 쓰이는 알고리즘 입니다. 두개의 알고리즘을 적용하는 경우는 노드의 각 간선 간 데이터 흐름이나 특정 병목이 있을 때 출발 노드와 도착노드 사이의 간선에서 어떤 지점이 가장 많은 흐름을 가지는지를 파악하는 알고리즘인데요. 

 

두 알고리즘은 비슷하지만 세부적으로 보면 다른점이 있는데요. 여기서 둘이 공통적으로 사용되는 키워드는 "Augmenting path" - "증강 경로" 입니다.

 

여기서 증강 경로를 각 순회마다 어떻게 선택하냐에 따라 포드퍼커슨과 에드몬드 카브 알고리즘이 나뉘는데요 더 자세히 알아보도록 하겠습니다.

---

Ford-Fulkerson 알고리즘

 

Ford-Fulkerson은 그리디(Greedy) 알고리즘에 기반한 방법입니다.

반복적으로 증강되는 경로를 찾아 capacity를 수정해 나아가 더 나은 경로를 찾는 방법입니다.

프로세스는 더이상 증강 될 수 있는 경로를 찾을 수 없을 때 까지 반복되는데 가장 단순하고 무식하게 순회하는 방식입니다.

 

그러나 이 알고리즘의 단점은 동일한 가중치로 여러가지의 옵션이 생길 때 어느 경로를 선택해야 하는지 제시하지를 못하는 단점이 있습니다. 만약 동일 가중치라 하더라고 반복 횟수가 더 많은 방법이 있을 수 도 있는 반면 더 적은 횟수의 반복으로 같은 가중치를 낼 수 있는 경로가 있지만 이 두개의 우위를 못가린다는 말입니다.

 

따라서 이 점을 해결하기 위해 Edmons-Karp 알고리즘이 나온겁니다.

 

복잡성(DFS) - O(fE). f - 최대 흐름, E -  간선

---

 

Edmons-Karp 알고리즘, 쉽게 이해하기 💧

네트워크에 물을 최대로 흘려보내는 문제를 푼다고 상상해 보세요. 각 파이프(간선)는 정해진 용량(최대 흐름)이 있고, 물을 보내는 시작점(Source)과 물을 받는 도착점(Sink)이 있습니다. Edmons-Karp 알고리즘은 이 네트워크에 물을 얼마나 최대로 보낼 수 있는지 계산하는 똑똑한 방법입니다.

---

핵심 아이디어: 가장 짧은 길부터 공략하기 (출처)

기존 방식(포드-풀커슨)은 깊이 우선 탐색(DFS)을 사용해서 물을 보낼 길을 찾습니다. 이건 마치 미로를 탐험할 때 한쪽 길로 무작정 깊이 들어가 보는 것과 같아요. 운이 나쁘면 아주 길고 비효율적인 경로를 선택할 수 있고, 이러면 전체 효율이 떨어집니다. [01:48]

반면, Edmons-Karp 알고리즘은 너비 우선 탐색(BFS)을 사용합니다. 이것은 시작점에서부터 한 칸, 두 칸... 이렇게 주변을 넓혀가며 가장 가까운, 즉 가장 적은 파이프를 거치는 최단 경로를 먼저 찾아냅니다. [03:09]

왜 최단 경로가 좋을까요? 길고 구불구불한 경로로 물을 먼저 보내면, 그 경로에 있는 파이프들이 일찍 채워져 버립니다. 그런데 그 파이프들이 나중에 다른 더 좋은 경로의 일부였다면 손해겠죠? 최단 경로를 우선으로 사용하면 자원을 더 효율적으로 배분하여 전체적으로 더 많은 물을 보낼 방법을 빨리 찾을 수 있습니다.

---

알고리즘 동작 방식 (수도 파이프 비유)

1. 길 찾기 (BFS): 수도꼭지(시작점)에서부터 하수구(도착점)까지 물이 흐를 수 있는 가장 짧은 경로를 찾습니다. 이때, 아직 용량이 남아있는 파이프(흐름 > 0)로만 길을 찾습니다.
2. 병목 찾기: 찾은 경로에서, 물을 가장 적게 흘려보낼 수 있는 '가장 좁은 파이프'의 용량, 즉 병목(bottleneck)을 확인합니다. [05:54]
3. 물 흘려보내기:
   • 찾아낸 병목 용량만큼 경로에 물을 흘려보냅니다.
   • 경로에 포함된 모든 파이프의 용량에서 이 병목 용량을 빼줍니다 (정방향).
   • 반대 방향으로는 같은 양을 더해줍니다 (역방향). 이 '역방향' 개념은 중요해요. 혹시 잘못된 경로로 물을 보냈을 때, 이 역방향 용량을 이용해 "물 흐름을 취소"하고 다른 길로 보낼 기회를 만들기 때문입니다.
4. 반복: 더 이상 시작점에서 도착점까지 물을 보낼 수 있는 경로가 없을 때까지 1~3번 과정을 계속 반복합니다.
5. 결과: 각 단계에서 흘려보낸 물의 양(병목 값들)을 모두 더하면, 그것이 바로 이 네트워크가 최대로 흘려보낼 수 있는 물의 양, 즉 최대 유량(Max Flow)이 됩니다. [08:03]

---

복잡성: O(V·E²)

• V (Vertex): 정점의 개수 (수도 시스템의 분기점)
• E (Edge): 간선의 개수 (파이프의 개수)

이 알고리즘은 BFS를 사용해 최단 경로를 찾기 때문에, 파이프 용량이 아무리 커도 일정한 계산 횟수 안에 답을 찾을 수 있습니다. 그래서 DFS를 사용할 때보다 훨씬 안정적이고 빠른 성능을 보장합니다. [02:31]

요약하자면, Edmons-Karp는 "무작정 아무 길이나 찾지 말고, 가장 짧은 길을 계속 찾아서 물을 보내자!" 라는 간단하고 효율적인 아이디어를 기반으로 한 알고리즘입니다.

 

 

코드:

import heapq
from collections import deque
from typing import List, Dict, Tuple, Optional

class Node:
    def __init__(self, name : str):
        self.name = name
        self.adjacent_nodes : Dict['Node', int] = {}

    def get_name(self) -> str:
        return self.name
    
    def get_adjacent_nodes(self) -> Dict['Node', int]:
        return self.adjacent_nodes

    def add_adjacent_nodes(self, node: 'Node', weight : int):
        self.adjacent_nodes[node] = weight
    

#This determines the shortest path - 용량이 0보다 큰 간선만을 따라 증가 경로 찾기
def bfs(
        s : Node, #시작
        t : Node, #끝
        parent : Dict[Node, Optional[Node]], #그래프
        visited : Dict[Node, bool]) -> bool: #방문 그래프

    queue = deque()
    queue.append(s)
    visited[s] = True

    while queue:
        current_node : Node = queue.popleft()
        for neighbor, capacity in current_node.get_adjacent_nodes().items():
            #And value is larger
            if not visited[neighbor] and capacity > 0:
                visited[neighbor] = True
                parent[neighbor] = current_node
                queue.append(neighbor)
                if neighbor == t:
                    return True
    return False


#Find a manximum flow  betweeb source - sink
def edmonds_karp(graph: Dict[str, Dict[str, int]], source: str, sink: str) -> int:
    #노드화
    nodes = {name: Node(name) for name in graph.keys()}

    #노드 연결, 잔여 그래프(Residual Graph) - 역방향 간선 추가. u - 현재노드, v - 이웃 노드
    for u_name, neighbors in graph.items():
        for v_name, capacity in neighbors.items():
            u, v = nodes[u_name], nodes[v_name]
            #정방향 추가
            u.add_adjacent_nodes(v, capacity)
            #역방향 추가 - 초기 0으로 세팅            
            if u not in v.get_adjacent_nodes(): #만약 역으로 가는 방향이 있다면
                v.add_adjacent_nodes(u, 0)

    #시작 노드 지정
    source_node = nodes[source]
    #끝나는 노드 지정
    sink_node = nodes[sink]
    #최대 유량
    max_flow : int = 0

    #증가 경로가 없을 때 까지 반복
    while True:
        #각 반복마다 parent와 visited 초기화
        parent = {node : None for node in nodes.values()}
        visited = {node : False for node in nodes.values()}

        #BFS를 통해 s -> t 경로 탐색
        if not bfs(source_node, sink_node, parent, visited):
            break #경로가 없으면 종료

        #경로 병목 용량 계산 - 끝점에서 시작지점까지 역 traverse
        path_flow = float('inf')
        v = sink_node
        while v != source_node:
            u = parent[v] #이전 간선
            # u -> v 간선 중 최솟값 찾기
            path_flow = min(path_flow, u.get_adjacent_nodes()[v])
            v = u

        #병목을 찾으면 용량만큼 전체 흐름(max_flow)에 추가
        max_flow += path_flow

        #잔여 그래프 업데이트
        v = sink_node
        while v != source_node:
            u = parent[v]
            u.get_adjacent_nodes()[v] -= path_flow
            v.get_adjacent_nodes()[u] += path_flow
            v = u
            
    return max_flow
        

if __name__ == '__main__':
    #Directed graph
    first_graph = {
        'S': {'A': 10, 'C': 10},
        'A': {'B': 4, 'C': 2, 'D': 8},
        'B': {'T': 10},
        'C': {'D': 9},
        'D': {'B': 6, 'T': 10},
        'T': {}
    }
    
    print(edmonds_karp(first_graph, 'S', 'T'))

 

 

위의 문제의 답으로 최대 우량이 19가 나옵니다.

---

 

그러면 모든 그래프 순회에서 Edmons-Karp 알고리즘이 답인가?

 

아닙니다, 경로가 음수인 경우 적용을 못하는 단점이 있습니다. 경로의 가중치가 음수인 경우 "보상"이라고 보면 될 것입니다. 애초에 애드몬드 카프 알고리즘이 적용되는 문제는 각 경로가 다룰 수 있는 흐름의 최대 용량을 확인하는 것이기 때문에 음수의 경로를 가정하지 않습니다.

 

만약 방대한 네트워크 환경에서 속도가 중요한 경우의 경로 탐색은 Dinic's algorithm 이라고 대안점이 있습니다. 해당 알고리즘은 다음에 다루도록 하겠습니다.