에드먼즈-카프 알고리즘
에드먼즈-카프 알고리즘은 잔여 네트워크에서 BFS로 가장 적은 간선 수의 증가 경로를 선택하는 포드-풀커슨 알고리즘의 구현이다 최대 유량·그래프 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의...
| 분류 | 알고리즘 · 최대 유량·그래프 알고리즘 |
|---|---|
| 목적 | 잔여 네트워크에서 BFS로 가장 적은 간선 수의 증가 경로를 선택하는 포드-풀커슨 알고리즘의 구현이다 |
| 처리 방식 | 출발점에서 도착점까지 증가 경로를 BFS로 찾고 경로의 최소 잔여 용량만큼 유량을 증가시킨다 |
| 복잡도·성능 | O(VE²) 시간, O(V+E) 탐색·네트워크 보조 공간 |
| 필수 조건 | 음수가 아닌 용량과 흐름 보존·잔여 네트워크의 일관성이 필요하다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
에드먼즈-카프 알고리즘은 잔여 네트워크에서 BFS로 가장 적은 간선 수의 증가 경로를 선택하는 포드-풀커슨 알고리즘의 구현이다 최대 유량·그래프 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 출발점에서 도착점까지 증가 경로를 BFS로 찾고 경로의 최소 잔여 용량만큼 유량을 증가시킨다. 역간선의 잔여 용량도 함께 갱신하여 이전 흐름을 되돌릴 수 있게 한다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 O(VE²) 시간, O(V+E) 탐색·네트워크 보조 공간 올바르게 적용하려면 음수가 아닌 용량과 흐름 보존·잔여 네트워크의 일관성이 필요하다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 최대 유량·최소 컷 문제에 사용한다. 임의 증가 경로를 택하는 방법보다 경로 길이에 대한 다항 시간 보장이 존재한다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]