Edmonds-Karp
이 글의 목차
← 기록 / 알고리즘 / 그래프

Edmonds-Karp

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

Edmonds-Karp

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

Time Complexity

  • Basic Flow Algorithm (Reference): O(fE)O(fE)
  • Worst: O(VE2)O(VE^2) (상한 - 실제로는 더 빠르다.)
    • 증가 경로를 최대 VEVE 번 이상 찾지 않고(증명되어 있음), 한번 찾을때 최대 EE 개의 Edge를 거칠 수 있으므로 나오는 시간복잡도
AI로 읽기 · Markdown
Markdown 열기 ↗
curl -fsSL 'https://www.readiz.com/notes/algorithm/graph/edmonds-karp/index.md'

서비스 열기

열기 방식을 선택해 주세요.

새 브라우저 탭에서 열기현재 화면을 유지하며 별도 탭에서 사용합니다.

로그인이 필요하거나 창 안에서 열리지 않는 서비스는 새 브라우저 탭에서 열어 주세요.