포드-풀커슨 알고리즘
포드-풀커슨 알고리즘은 용량이 정의된 네트워크에서 잔여 경로를 따라 유량을 증가시켜 최대 유량을 찾는다 그래프 알고리즘의 최대 유량 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전제는...
| 분류 | 알고리즘 · 그래프 알고리즘 · 최대 유량 |
|---|---|
| 문제 | 용량이 정의된 네트워크에서 잔여 경로를 따라 유량을 증가시켜 최대 유량을 찾는다 |
| 입력 | 용량이 음수가 아니어야 하며 흐름 보존 조건을 만족해야 한다 |
| 핵심 단계 | 원본 간선과 역간선의 잔여 용량을 구성하고 출발점에서 도착점까지 증가 경로를 찾는다 |
| 시간 복잡도 | 정수 용량 O(E|f*|) |
| 공간·구현 | 정수 용량에 DFS 증가 경로 사용 시 O(E|f*|); 일반 실수 용량은 종료 보장 문제가 있다 |
| 관련 분야 | 그래프, 자료구조 |
| 참고 문헌 | MIT Algorithms |
포드-풀커슨 알고리즘은 용량이 정의된 네트워크에서 잔여 경로를 따라 유량을 증가시켜 최대 유량을 찾는다 그래프 알고리즘의 최대 유량 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전제는 용량이 음수가 아니어야 하며 흐름 보존 조건을 만족해야 한다.[1]
핵심 절차는 원본 간선과 역간선의 잔여 용량을 구성하고 출발점에서 도착점까지 증가 경로를 찾는다. 경로에서 가능한 최소 잔여 용량만큼 유량을 늘린다. 구현에서는 각 정점 또는 간선에 기록된 상태가 어떤 의미를 갖는지 불변식을 정의하고, 탐색·갱신 과정에서 해당 상태를 일관되게 유지해야 한다.
계산 비용은 정수 용량에 DFS 증가 경로 사용 시 O(E|f*|); 일반 실수 용량은 종료 보장 문제가 있다 정점 수를 V, 간선 수를 E라고 나타낼 때 정수 용량 O(E|f*|)의 시간 특성을 가진다. 저장 공간은 그래프의 표현 방식, 큐·스택·우선순위 큐 및 결과 배열의 선택에 영향을 받으므로 실제 적용 시 구현 구조를 함께 분석한다.
최대 유량·최소 컷 정리를 구현적으로 설명한다. 에드먼즈-카프 알고리즘은 BFS 경로를 선택해 다항 시간 보장을 얻는다. 대표적인 변형 알고리즘 및 자료구조의 선택은 결과의 최적성, 음수 가중치나 사이클의 허용 여부, 희소·밀집 그래프 여부에 따라 달라진다. 동점 처리와 비연결 그래프 등의 경계 사례까지 정의해야 구현 결과가 명확해진다.[2]