에드먼즈-카프 알고리즘

컴퓨터 과학에서, Edmonds-Karp 알고리즘은 흐름 네트워크의 최대 $흐름$을${\displaystyle }$O ($V$ ${\displaystyle {}^{\mathrm{}}}$ 2$){\displaystyle O(V$ E$^{2$}) 시간$$ 단위로 계산하기 위한 Ford-Fulkerson 방법의 구현이다.이 알고리즘은 예핌 디니츠(이름도 번역된 E)에 의해 처음 발표되었다.A. 다이닉"은 1970년에 특히^[1][2] 그의 초기 논문들의 저자로써 1972년에 잭 에드먼즈와 리차드 카프가 독자적으로 출판했다.^[3]Dinic의 알고리즘에는 실행 시간을 $O{\displaystyle }$(${\displaystyle V}$ ${\displaystyle 2{}^{}}$ E$){\displaystyle O(V ^{2} E )}$로 줄이는 추가 기법이 포함되어 있다$.$^[2]

Wikibook 알고리즘 구현에 대한 주제가 있는 페이지: Edmonds-Karp

알고리즘.

증가 경로를 찾을 때의 검색 순서가 정의된 것을 제외하고, 알고리즘은 Ford-Fulkerson 알고리즘과 동일하다.발견된 경로는 가용 용량이 있는 최단 경로여야 한다.이것은 넓이 우선 검색으로 찾을 수 있는데, 여기서 우리는 각 가장자리에 1의 무게를 가한다.$O{\displaystyle (V}$ ${\displaystyle E}$ ${\displaystyle {}^{\mathrm{}}}$) ${\displaystyle O(V$ E ^{$2}})$의 실행 시간은 각 $증강{\displaystyle }$ 경로를 O${\displaystyle (E}$)$${\$displaystyle$ O$(E )}$ 시간에서$$ 찾을 수 있으며, $매번{\displaystyle }$ E ${\displaystyle E}$ 가장자리$$ 중 적어도 하나가 포화(가능한 최대 흐름을 가진 가장자리) 상태가 됨을 보여줌으로써 확인된다$$.포화 에지에서 증배 경로를 따라 선원까지의 거리는 포화 시간보다 길어야 하며 길이가 ${\displaystyle 최대}$ V $displaystyle$V$}.$ 이 알고리즘의 또 다른 특성은 최단 증배 경로의 길이가 단조롭게 증가한다는 것이다$.$알고리즘 소개에는 접근 가능한 증거가 있다.^[4]

가성음

알고리즘 EdmondsKarp은 입력: 그래프(그래프[v]는 원래 그래프에서 꼭지점 v에서 나오는 에지와 푸시백 흐름에 사용되는 해당 구성 후진 에지의 목록이어야 한다. 각 에지는 역 에지에 대한 포인터뿐만 아니라 파라미터로서 용량, 흐름, 소스 및 싱크(sink)를 가져야 한다.) s (소스 정점) t (싱크 정점) 출력: 흐름 (최대 흐름의 값) 흐름 := 0 (0으로 흐름 초기화) 반복 (bfs)를 실행하여 가장 짧은 s-t 경로를 찾는다.그래서 우리는)q:)q.push(s)pred queue():)array(graph.length)지 않으나 empty(q)똥개:)에지 e를 위해 graph[똥개]에 q.pull()만약 pred[e.t])이 아무 가치가 없고 e.t s, 그리고 e.cap 을≠, e.flow 다음 경로를 나중에 복구할 수 있는 우리는 가장자리 각 꼭지점에 오르기 위해 취하저장하기''pred을 사용한다.                     p적색[e.t] := e.push(e.t)가 아니라면 (pred[t] = null) 그때 (증강 경로를 찾았다. See how much flow we can send)              df := ∞ for (e := pred[t]; e ≠ null; e := pred[e.s]) do                 df := min(df, e.cap - e.flow)             (And update edges by that amount) for (e := pred[t]; e ≠ null; e := pred[e.s]) do                 e.flow  := e.flow + df                 e.rev.flow := e.rev.flow - df             flow := flow + df 이전[t] = null(즉, 증가 경로를 찾을 수 없을 때까지) 반환 흐름

예

다음과 같이 소스 A, 싱크 G 및 용량 등 7개 노드로 구성된 네트워크 제공:

가장자리에 $쓰인$ f /${\displaystyle c}$ ${\displaystyle f/c}$ 쌍에서 $f{\displaystyle }$ ${\displaystyle f}$은 전류 흐름이고 c ${\displaystyle c}$은 용량이다$$.$u{\displaystyle }$ ${\displaystyle u}$에서 $v{\displaystyle }$ ${\displaystyle v}$까지의 잔여 용량은 ${\displaystyle c_{}}$ (${\displaystyle u}$ , ${\displaystyle v}$) = ${\displaystyle c}$(${\displaystyle u}$, v )${\displaystyle }$- ${\displaystyle f}$ (${\displaystyle u}$ ,$v$) ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$, 총 용량이다$$.$u{\displaystyle }$ ${\displaystyle$ $u$$}$에서 $v{\displaystyle }$ ${\displaystyle$ v$}($으)로의$$ 순 흐름이 음수인$$ 경우 잔존 용량에 기여한다.

역량	경로	결과 네트워크
${\displaystyle {\begin}&\min(c_{f})(A,D),c_{f}(D,E),c_{f}(E,G))\\=&\min(3-0,2-0,1-0)=\\&\min(3,2,1)=1\end{arged}}}$	$A,D,E,G}$
${\displaystyle {\begin}&\min(c_{f})(A,D),c_{f}(D,F),c_{f}(F,G)\=&\min(3-1,6-0,9-0)\=&\in(2,6,9)=2nd}정렬}}}}}$	$A,D,F,G}$
${\displaystyle {\begin{aligned}&\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-0,4-0,1-0,6-2,9-2)\\=&\min(3,4,1,4,7)=1\end{aligned}}}$	$A,B,C,D,F,G}$
${\displaystyle {\begin{aligned}&\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-1,4-1,2-0,0-(-1),6-3,9-3)\\=&\min(2,3,2,1,3,6)=1\end{aligned}}}$	$A,B,C,E,D,F,G}$

알고리즘에 의해 발견된 증가 경로의 길이(빨간색)가 어떻게 감소하지 않는지 주목하십시오.발견된 경로가 가장 짧다.발견된 흐름은 선원과 싱크대를 구분하는 그래프의 최소 절단면에 걸친 용량과 동일하다.이 그래프에는 최소 절단이 하나 있을 뿐이며, 노드를 용량으로 $\{{\displaystyle A,}$ B${\displaystyle ,}$ ${\displaystyle C,}$ ${\displaystyle E\}}$ ${\displaystyle \{A,B,C,E\}$ 및$$${\displaystyle }${${\displaystyle D,F,G\}}$ ${\displaystyle \{D,F,G$ 세트로 분할한다.

${\displaystyle c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\ }$

메모들

참조

1. 알고리즘 및 복잡성(63~69페이지 참조)https://web.archive.org/web/20061005083406/http://www.cis.upenn.edu/~wilf/AlgComp3.html