Ford-Fulkerson 알고리즘
Ford-Fulkerson 알고리즘
1. 개념
Ford-Fulkerson 알고리즘은 네트워크 유량 문제에서 최대 유량을 구하는 알고리즘이다. 이 알고리즘의 목표는 시작점에서 끝점까지 흐를 수 있는 최대 유량을 찾는 것이다.
아이디어는 가능한 경로(augmenting path)를 찾아서 유랑을 점점 늘려가는 방식이다.
2. 용어
- Flow Network : 각 간선에 용량(capacity)이 주어진 방향 그래프
- Flow(유량) : 각 간선을 통해 실제로 흘려보내는 값
- Augmenting path(증가 경로) : 아직 용량 여유가 있는 경로
- residual capacity(잔여 용량) : 전체 용량 - 현재 유량
- back edge(역방향 간선) : 유량을 줄일 수 있는 방향의 간선
3. 동작 원리
- 초기화 : 모든 간선의 유량을 0으로 설정
- 증가 경로 찾기 : 현재 잔여 용량이 0보다 큰 경로를 시작점부터 끝점까지 찾음
- 유량 추가 : 해당 경로에서 가장 작은 잔여 용량을 경로 전체에 더함
- 잔여 용량 갱신 : 순방향 간선의 잔여 용량을 줄이고, 역방향 간선의 잔여 용량을 늘림
- 반복 : 더 이상 증가 경로가 없을 때까지 위 과정을 반복
- 모든 증가 경로가 소진되면 현재의 유량 합이 최대 유량이 됨
4. 예시 (백준 #6086) 최대 유량
5
A B 3
B C 3
C D 5
D Z 4
B Z 6
(단 A가 시작점 Z가 끝점이다.)