Edmonds-Karp

Ford-Fulkerson 방법을 BFS로 구현한 것을 Edmonds-Karp Algorithm이라고 한다.

이 글의 목차

Ford-Fulkerson 방법을 BFS로 구현한 것을 Edmonds-Karp Algorithm이라고 한다.

Time Complexity

Basic Flow Algorithm (Reference): $O(fE)$
Worst: $O(VE^2)$ $O (V E^{2})$ (상한 - 실제로는 더 빠르다.)
- 증가 경로를 최대 $VE$ 번 이상 찾지 않고(증명되어 있음), 한번 찾을때 최대 $E$ 개의 Edge를 거칠 수 있으므로 나오는 시간복잡도

이전 사이트에서 옮긴 글입니다. 원본 보관본

AI로 읽기 · Markdown

로그인 없이 읽는 Markdown 원문.

curl -fsSL 'https://www.readiz.com/notes/algorithm/graph/edmonds-karp/index.md'