Ford-Fulkerson / Edmonds-Karp / Dinic 비교

Ford-Fulkerson / Edmonds-Karp / Dinic 비교

최대 유량 문제를 해결하는 대표적 세 알고리즘으로, 증가 경로 탐색 방법과 시간 복잡도에서 차이

Ford-Fulkerson 방법

• •DFS로 증가 경로 탐색, 잔여 용량만큼 유량 증가 반복
• •시간 복잡도: O(E × max_flow), 정수 용량 시 종료 보장
• •단점: 실수 용량 시 무한 루프 가능, 비효율적 경로 선택 가능

Edmonds-Karp 알고리즘

• •Ford-Fulkerson + BFS(최단 증가 경로, 간선 수 기준)
• •시간 복잡도: O(VE²), 용량 무관 다항 시간 보장
• •장점: 구현 단순, 안정적 성능, Ford-Fulkerson 개선

Dinic 알고리즘

• •BFS로 레벨 그래프(Level Graph) 구축 → DFS로 차단 유량(Blocking Flow) 탐색
• •시간 복잡도: O(V²E), 단위 용량 네트워크 O(E√V)
• •장점: 대규모 네트워크에 효율적, 이분 매칭에 최적

비교 표

연관: 최대 유량, 잔여 그래프, 증가 경로, 레벨 그래프, 최소 컷