앞서 다루었던 에드몬드-카프 알고리즘이 "배관망에서 목적지까지 얼마나 많은 물을 쏟아부을 수 있는가?"라는 '최대 유량'에만 집착했다면, 현실 세계의 네트워크 문제는 한 차원 더 높은 최적화를 요구합니다. 물건을 운송할 때 도로마다 통행료(비용)가 존재하고, 통과할 수 있는 트럭의 대수(용량)도 정해져 있습니다. "도착지까지 물건을 최대한 많이 보내되(Max Flow), 그 과정에서 발생하는 배송 비용을 최소화(Min Cost)하라!" 이 두 마리 토끼를 동시에 완벽하게 잡아내는 끝판왕 알고리즘이 바로 최소 비용 최대 유량(Min-Cost Max-Flow, 이하 MCMF)입니다. 네트워크 플로우와 최단 거리 탐색(Shortest Path)이 결합된 이 우아한 하이브리드 알고리즘의 동작 원리를 낱낱이 파헤쳐 보겠습니다.
1. 용량(Capacity)과 비용(Cost)의 이중주
MCMF의 그래프 간선에는 이제 capacity(최대 용량)와 함께 cost(유량 1을 흘려보낼 때 발생하는 비용)라는 두 개의 지표가 달립니다. 기본 골격은 기존의 네트워크 플로우와 동일합니다. "출발지(S)에서 도착지(T)로 갈 수 있는 경로(여유 용량이 있는 길)를 찾아 물을 흘려보낸다."
하지만 차이점은 '어떤 길을 먼저 찾을 것인가'에 있습니다. 최대 유량을 구하는 에드몬드-카프는 단순히 '간선이 가장 적은 길(BFS)'을 찾았지만, MCMF는 '단위 비용의 합이 가장 저렴한 길'을 찾아야 합니다. 즉, 유량을 보낼 경로를 찾을 때 BFS가 아니라 최단 거리 탐색 알고리즘을 사용해야 합니다.
2. BFS 대신 다익스트라? 아니, SPFA의 도입!
가장 저렴한 경로를 찾아야 하니 다익스트라(Dijkstra) 알고리즘을 쓰면 될 것 같지만, 여기에는 치명적인 함정이 숨어 있습니다. 바로 네트워크 플로우의 꽃인 '음의 유량(역방향 간선)' 때문입니다.
2-1. 역방향 간선과 음수 비용(Negative Cost)
물을 보냈다가 길을 잘못 들었음을 깨닫고 물을 취소(환불)하기 위해 역방향으로 잔여 간선을 만들 때, 용량만 거꾸로 뚫리는 것이 아닙니다. 비용(Cost) 역시 마이너스(-)로 적용되어야 합니다. A에서 B로 갈 때 비용이 10이었다면, 나중에 역방향 간선을 타고 B에서 A로 유량을 돌려보낼 때는 비용이 -10이 되어, 지불했던 통행료를 환불받아야 정상적인 계산이 성립합니다.
이처럼 그래프에 음수 가중치 간선이 필연적으로 발생하기 때문에, 음수 간선을 처리하지 못하는 다익스트라 알고리즘은 절대 사용할 수 없습니다. 따라서 벨만-포드(Bellman-Ford) 알고리즘이나, 이를 큐(Queue)를 이용해 O(V * E)의 평균 속도로 비약적으로 최적화한 SPFA(Shortest Path Faster Algorithm)가 MCMF의 심장으로 채택됩니다.
3. MCMF의 완벽한 순환 시뮬레이션
이제 만반의 준비가 끝났습니다. MCMF는 다음과 같은 단계를 유량을 더 이상 보낼 수 없을 때까지 반복합니다.
- 잔여 용량이 0보다 큰 간선들만 이용하여, SPFA 알고리즘으로 출발지(S)에서 도착지(T)까지 가는 비용(Cost)이 가장 저렴한 최단 경로를 찾습니다.
- 경로를 찾지 못했다면(도달 불가), 모든 유량을 쥐어짜 낸 것이므로 루프를 종료합니다.
- 경로를 찾았다면, 그 경로상에서 통과할 수 있는 가장 좁은 병목 용량(Min Capacity)을 구합니다.
- 병목 용량만큼 경로를 따라 물을 흘려보냅니다. (이때 총비용에
보낸 유량 * 경로의 총비용을 더해줍니다.) - 물이 흐른 반대 방향으로 환불을 위한 역방향 간선(비용은 음수)을 뚫어줍니다.
가장 싼 경로를 그리디하게 찾고, 실수했다면 음수 간선을 통해 환불받으며 더 나은 길을 개척하는 이 놀라운 과정을 거치면, 최종적으로 네트워크가 허용하는 가장 꽉 찬 유량을, 세상에서 가장 저렴한 비용으로 운송해 내는 완벽한 최적해가 도출됩니다.
1. MCMF(최소 비용 최대 유량)는 유량 네트워크에서 흐름을 최대화하면서 발생하는 총비용(Cost)을 최소화하는 하이브리드 최적화 알고리즘입니다.
2. 일반 유량 탐색 시 사용하는 BFS 대신, 단위 비용을 가중치로 삼아 가장 저렴한 경로를 먼저 찾는 방식을 취합니다.
3. 역방향 잔여 간선 생성 시 음수의 비용(환불 처리)이 발생하므로 다익스트라가 아닌 SPFA(혹은 벨만-포드) 최단 거리 탐색을 사용하여 경로를 계속 갱신하는 것이 핵심입니다.