Max Flow Algorithm

이번 글에서는 최대 유량 알고리즘(Max Flow Algorithm) 을 포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)을 중심으로 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다. 최대 유량 알고리즘이란 가중치가 있는 방향그래프(directed graph) $G$와 시작(source) 노드 $s$, 도착(sink) 노드 $t$가 주어졌을 때 각 엣지의 용량(capacity)을 고려하여 $s$에서 $t$로 흘려보낼 수 있는 최대 유량(flow)을 구하는 알고리즘을 가리킵니다.