네트워크 플로우 알고리즘: Ford-Fulkerson과 Edmonds-Karp

네트워크 플로우 문제를 시각적으로 나타낸 다이어그램

네트워크 플로우 문제란?

네트워크 플로우 문제는 네트워크 내에서 “흐를 수 있는 물리적 양”을 구하는 문제입니다. 이는 주로 물류, 교통, 통신 네트워크에서 발생하며, 특정 출발점에서 목적지까지 최적의 흐름을 계산하는 문제로, 여러 실용적인 분야에서 사용됩니다.

핵심 개념

• 정점(Vertex): 네트워크에서의 각 개별적인 지점.
• 간선(Edge): 두 정점을 연결하는 경로.
• 용량(Capacity): 각 간선이 운반할 수 있는 최대 흐름량.
• 흐름(Flow): 네트워크 내에서 각 간선을 따라 흐르는 양.

Ford-Fulkerson 알고리즘

Ford-Fulkerson 알고리즘은 네트워크 플로우 문제를 해결하는 가장 기본적인 방법으로, 최대 유량을 구하는 데 사용됩니다. 이 알고리즘은 잔여 용량(Residual Capacity)을 이용하여 경로를 찾고, 경로를 따라 흐름을 증가시키는 방식으로 동작합니다.

Ford-Fulkerson 알고리즘의 주요 절차

1. 잔여 용량 계산: 모든 간선에 대해 최대 용량을 기준으로 잉여 용량을 계산합니다.
2. 증가 경로(augmenting path) 찾기: 출발점에서 목적지까지 흐를 수 있는 경로를 찾아냅니다. 경로는 잉여 용량이 있는 간선으로만 구성됩니다.
3. 흐름 증가: 경로가 발견되면 그 경로에 대해 최대 흐름을 증가시키고, 각 간선의 잉여 용량을 업데이트합니다.
4. 반복: 더 이상 증가 경로가 없을 때까지 위 단계를 반복합니다.

문제점과 한계

Ford-Fulkerson 알고리즘은 경로를 선택하는 방식에 따라 성능이 달라질 수 있습니다. 예를 들어, 선택한 경로가 최단 경로가 아닐 경우, 알고리즘은 시간 복잡도가 매우 커질 수 있습니다. 또한, 간선에 용량이 실수로 주어졌을 때 이 알고리즘은 무한 루프에 빠질 수 있습니다.

Edmonds-Karp 알고리즘

Edmonds-Karp 알고리즘은 Ford-Fulkerson 알고리즘을 개선한 알고리즘입니다. 주요 차이점은 너비 우선 탐색(BFS)을 사용하여 증가 경로를 찾는 방식입니다. 이로 인해 최단 경로를 찾을 수 있으며, 더 안정적이고 효율적인 성능을 제공합니다.

Edmonds-Karp 알고리즘의 주요 절차

1. BFS로 증가 경로 찾기: BFS를 사용해 출발점에서 목적지까지 가는 최단 경로를 찾습니다. 이 경로는 최소 용량을 가진 간선이 포함된 경로입니다.
2. 흐름 증가: 경로가 발견되면, 해당 경로를 따라 흐름을 증가시키고, 잉여 용량을 갱신합니다.
3. 반복: 더 이상 증가 경로가 없을 때까지 위 단계를 반복합니다.

Edmonds-Karp의 시간 복잡도

Edmonds-Karp 알고리즘은 O(VE²) 의 시간 복잡도를 가집니다. 여기서 V는 정점의 수, E는 간선의 수입니다. 이 알고리즘은 Ford-Fulkerson보다 성능이 향상되었지만, 여전히 대규모 네트워크에서는 성능상의 한계가 있을 수 있습니다.

Ford-Fulkerson vs Edmonds-Karp

• 단순성: Ford-Fulkerson은 구현이 비교적 간단하지만, 경로 선택에 따라 성능이 달라질 수 있습니다.
• 성능: Edmonds-Karp는 BFS를 사용하여 항상 최단 경로를 찾아가므로 Ford-Fulkerson보다 더 안정적이고 예측 가능한 성능을 보입니다.
• 시간 복잡도: Ford-Fulkerson은 경로 선택 방식에 따라 달라지므로 최악의 경우 시간 복잡도가 매우 클 수 있습니다. 반면 Edmonds-Karp는 시간 복잡도가 O(VE²)로 보장되지만 여전히 큰 네트워크에서는 비효율적일 수 있습니다.

네트워크 플로우의 응용 분야

네트워크 플로우 알고리즘은 다양한 분야에서 응용될 수 있습니다. 주요 응용 분야는 다음과 같습니다.

• 물류 및 운송: 여러 물류 경로 중 최적의 흐름을 계산하여 비용을 절감할 수 있습니다.
• 통신 네트워크: 데이터를 네트워크 내에서 최적의 경로로 흐르게 하여 효율성을 높이는 데 사용됩니다.
• 일자리 배정: 각 작업을 적절한 일꾼에게 할당하여 최대 효율을 이끌어낼 수 있습니다.
• 자동화된 시스템: 자원의 할당 및 제어 시스템에서 유용한 도구로 활용됩니다.

최적화된 네트워크 플로우 문제를 해결하는 방법

실제 시스템에서 더 큰 문제를 다룰 때는 선택적 알고리즘을 사용해 해결할 수 있습니다. 예를 들어, Push-Relabel 알고리즘은 아주 큰 네트워크에서도 유효하게 작동하는 고급 알고리즘입니다.

또한, 대규모 네트워크에서는 병렬 처리와 분산 처리를 이용해 계산 효율을 높일 수 있는 방법도 연구되고 있습니다.

마무리

네트워크 플로우 알고리즘은 많은 실용적인 문제를 해결하는 데 중요한 역할을 합니다. Ford-Fulkerson과 Edmonds-Karp는 네트워크 플로우 문제를 해결하는 데 널리 사용되는 두 가지 알고리즘으로, 각자의 특성과 용도에 따라 선택적으로 활용할 수 있습니다. 알고리즘을 제대로 이해하고 활용하는 것이 더 효율적인 문제 해결을 가능하게 합니다.

관련 유튜브 영상

• Ford-Fulkerson 알고리즘
• Edmonds-Karp 알고리즘