다이닉 알고리즘

디닉의 알고리즘 또는 디니츠의 알고리즘은 플로우 네트워크의 최대 흐름을 계산하기 위한 강력한 다항식 알고리즘으로, 이스라엘(구 소련)의 컴퓨터 과학자 예핌(Chaim) A가 1970년에 착안했다.디니츠.^[1]알고리즘은 $O{\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$) ${\displaystyle O(V^{2}E)}$번으로$$ 실행되며 최단 증강 경로를 사용한다는 점에서 O${\displaystyle (}V{\displaystyle }$ ${\displaystyle {E\mathrm{}}^{}}$ 2)${\displaystyle O(VE^{2})$번으로$$ 실행되는 Edmonds-Karp 알고리즘과 유사하다.레벨 그래프의 개념과 블록 흐름의 도입으로 다이닉의 알고리즘이 그 성능을 달성할 수 있게 되었다.

역사

예핌 디니츠는 아델슨-벨스키의 알고리즘 클래스에서 수업 전 연습에 대응하여 이 알고리즘을 발명했다.당시 그는 포드-풀커슨 알고리즘에 관한 기본적인 사실들을 알지 못했다.^[2]

디니츠는 자신의 알고리즘을 1969년 1월에 발명했다고 언급하는데, 이 알고리즘은 1970년에 Doklady Akademii Nauk SSSR에 발표되었다.1974년 하이파 테크니온의 시몬 이븐과 (당시 박사과정 학생) 알론 이타이는 디니츠의 알고리즘과 알렉산더 V. 카르자노프의 흐름을 차단하려는 관련 아이디어에 매우 호기심과 흥미를 느꼈다.그러나 그들이 이 두 논문을 해독하기는 어려웠는데, 각각 독레이디 아카데미 나우크 SSSR의 제약을 충족시키기 위해 4페이지로 제한되어 있다.심지어 포기하지 않았고, 3일간의 노력 끝에 계층화된 네트워크 유지보수 문제를 제외한 두 논문을 모두 이해할 수 있었다.이후 몇 년간 이븐은 '다이닉의 알고리즘'을 주제로 강연하면서 저자의 이름을 대중화하면서 잘못 발음했다.이븐과 이타이도 BFS와 DFS를 결합하여 이 알고리즘에 기여했는데, 이것이 현재 알고리즘이 보편적으로 제시되고 있는 방식이다.^[3]

포드-풀커슨 알고리즘이 발명된 후 약 10년 동안, 비합리적인 에지 용량의 일반적인 경우 다항 시간 내에 종료되도록 할 수 있을지는 알 수 없었다.이로 인해 일반적인 경우에서 최대 흐름 문제를 해결할 알려진 다항식 시간 알고리즘이 부족하게 되었다.디니츠의 알고리즘과 Edmonds-Karp 알고리즘(1972년 간행)은 모두 독립적으로 Ford-Fulkerson 알고리즘에서 각각의 증강 경로가 최단 경로인 경우, 증가 경로의 길이는 감소하지 않고 알고리즘은 항상 종료된다는 것을 보여주었다.

정의

Let ${\displaystyle G=((V,E),c,f,s,t)}$ be a network with ${\displaystyle c(u,v)}$ and ${\displaystyle f(u,v)}$ the capacity and the flow of the edge ${\displaystyle (u,v)}$, respectively.

잔여 용량은 다음과 같이 정의된$$ 매핑 $c{\displaystyle {}_{}}$ ${\displaystyle f_{}}$: ${\displaystyle V}$ ${\displaystyle \times }$ V${\displaystyle }$→ ${\displaystyle {}^{}}$+ ${\$ R$^{+}$이다.

1. if (${\displaystyle u}$, v${\displaystyle }$) ${\displaystyle \in }$ ${\displaystyle E}$ ${\displaystyle (u,v)\in$ E$\},$

   ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$

2. ${\displaystyle c_{}}$ ${\displaystyle f_{}}$ (${\displaystyle u}$ , v${\displaystyle }$)${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle c_{f}(u,v)=0}$ 이외의 경우$$.

잔차 그래프는 비가중 그래프 $G{\displaystyle {}_{}}$ ${\displaystyle f_{}}$=${\displaystyle }$(${\displaystyle (V}$, ${\displaystyle E_{}}$ ${\displaystyle f_{}}$) ,${\displaystyle {{}_{}}_{}c}$ ${\displaystyle {F_{}}_{}E}$ f${\displaystyle }$, s$$, t ) {\$displaystyle$G_${f}=((V,E_{f}),$c_{$f} _{E_{$f},s$,t)$이며$,$ 여기서,

={ ( , ) : : ( , )> $}$ {\$displaystyle E_{f}=\{(u,v)\in$V\$time$V\$colon$\;$c_{f}($u,$v)0\}$.

증강 경로는 잔차 그래프 $G{\displaystyle {}_{}}$ ${\displaystyle f_{}}$ ${\$에서 s ${\displaystyle s}$– ${\displaystyle }$ ${\displaystyle t}$ 경로 입니다$.$

Define ${\displaystyle \operatorname {dist} (v)}$ to be the length of the shortest path from ${\displaystyle s}$ to ${\displaystyle v}$ in ${\displaystyle G_{f}}$. Then the level graph of ${\displaystyle G_{f}}$ is the graph ${\displaystyle G_L=((V,E_L),c_f{}_{E_L},s}$${\displaystyle ,}$ ${\displaystyle t}$) ${\displaystyle G_{L}=(V,E_{L}),c_{f} _{E_},s,t$ 여기서

${\displaystyle E_{}}$ ${\displaystyle L_{}}$=${\displaystyle }${ (${\displaystyle u}$ , v${\displaystyle }$) ${\displaystyle \in }$ ${\displaystyle E_{}}$ f${\displaystyle {}_{}}$: ${\displaystyle \mathrm{distation}}$ ${\displaystyle }$( v${\displaystyle }$)${\displaystyle }$= ${\displaystyle \mathrm{distance}}$ ${\displaystyle }$ (${\displaystyle u}$)${\displaystyle }$+ ${\displaystyle 1}$} ${\displaystyle E_{L}=\{(u,v)\in E_{f}\colon$ \\colon \colon $\distername {dist}=\$dist$}(u)+1$dist}.

{s\displaystyle}fEL′과′{\displaystyle f'}는 그래프 G′)((V, EL′), s, t){\displaystyle G'=((V,E_{L}'),s,t)}t{\displaystyle지}흐름 – 블로킹 흐름은 s){(u, v):f′(u, v)<>요리 fEL(u, v)}{\displaystyle E_{나는}'=\{(u,v)\colon cm이다.;f'$(u,v)<c_{f}_{E_{L}(u,v)\}}}$에 s ${\displaystyle$s$}$–$$${\displaystyle }$ ${\displaystyle t}$ 경로가$$ 없음^{[Note 1][4]}

알고리즘.

다이닉 알고리즘

입력: 네트워크 $G{\displaystyle }$=${\displaystyle }$( ${\displaystyle (V}$, E${\displaystyle }$)${\displaystyle }$, c${\displaystyle }$, ${\displaystyle s}$, ${\displaystyle t}$) ${\displaystyle$ G$=((V,E),c,s,t$

출력: $$의 $s{\displaystyle }$ ${\displaystyle s}$– t ${\displaystyle t}$ $흐름$ f ${\displaystyle f}$

1. $각$ $e$에${\displaystyle }$대해 ${\displaystyle f}$ ${\displaystyle (}$$$e ) = 0 {\$displaystyle$ $f(e)=0}$을${\displaystyle (}$를$)$ 설정하십시오$.$
2. $G{\displaystyle }$ ${\displaystyle G}$의 $G{\displaystyle {}_{}}$ ${\displaystyle f_{}}$ ${\$에서 G $L{\displaystyle {}_{}}$ ${\$을 생성하십시오$.$ ${\displaystyle \mathrm{dist}}$ ${\displaystyle }$ ( ${\displaystyle t}$)${\displaystyle }$= ${\displaystyle \mathrm{\infty }}$ ${\displaysty \operatorname {dist$ $stop$ 및 $출력{\displaystyle }$ f ${\displaysty f$
3. $G{\displaystyle {}_{}}$ ${\displaystyle L_{}}$ ${\$에서 차단 흐름 $f{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ f$'}$을(를) 찾으십시오$.$
4. 증가 흐름 $f{\displaystyle }$ ${\displaystyle$ $f$$}$을(를) $f{\displaystyle {}^{}}$′ ${\$ f$'}$만큼$$ 추가하고$$ 2단계로 돌아가십시오.

분석

각 차단 흐름의 레이어 수가 매번 최소 1개씩 증가하므로 알고리즘에는 ${\displaystyle V}$- ${\displaystyle 1}$ ${\displaystyle$V$-1}$개의$$ 차단 흐름이 있음을 알 수 있다.각 항목에 대해:

• 레벨 그래프 $G{\displaystyle {}_{}}$ ${\displaystyle L_{}}$ ${\$은(는) $O{\displaystyle }$(${\displaystyle E}$ ${\displaystyle )}$ ${\displaystyle O(E)}$ 시간$$ 내에 너비 우선 검색으로 구성할 수 있다$$.
• 레벨 그래프 $G{\displaystyle {}_{}}$ ${\displaystyle L_{}}$ ${\$의 차단 흐름은 $O{\displaystyle }$(${\displaystyle V}$ E${\displaystyle }$) ${\displaystyle O(VE)}$시간에서$$^{[Note 2]} 확인할 수 있다$$.

각 계층에 대한$$ 총 실행 시간 $O{\displaystyle (E}$+ ${\displaystyle V}$ ${\displaystyle E}$)${\displaystyle }$= ${\displaystyle O(V}$ ${\displaystyle E}$) ${\displaystyle O(E+VE)=O(VE)}.$그 결과 다이닉 알고리즘의 실행시간은 O${\displaystyle }$($V{\displaystyle }$ ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ $){\displaystyle$O$(V^{2}E)}$ 입니다$.$^[5]

동적 트리라는 데이터 구조를 사용하면 각 단계에서 차단 흐름을 찾는 실행 시간을 $O{\displaystyle (E}$ ${\displaystyle \log }$ ${\displaystyle }$ V$){\displaystyle O(E\log$ V$)}$로 줄일 수 있으므로$$ Dinic 알고리즘의 실행 시간을 $O{\displaystyle (V}$ ${\displaystyle E}$ ${\displaystyle \log }$ ${\displaystyle }$ $){\displaystystyle O(VE\log$ V$)}$로 개선할 수 있다$.$

특례

단위 용량이 있는 네트워크에서, 훨씬 더 강한 시간 구속이 유지된다.각 차단 흐름은 $){\displaystyle O(E)}$시간에서$$ 확인할 수 있으며, 위상 $수$가${\displaystyle }$O$){\displaystyle$ O$({\sqrt{E})}$와${\displaystyle }$O(${\displaystyle {V2\mathrm{}}^{}}$/ 3$){\displaysty O(V^{2/3})$를 초과하지 않는 것을 알 수 있다$.$따라서 알고리즘은 $O{\displaystyle (최소}$ {${\displaystyle {V\mathrm{}}^{}}$ ${\displaystyle {}^{}}$/ ${\displaystyle {3\mathrm{}}^{}}$,${\displaystyle {}^{}{E\mathrm{}}^{}}$ ${\displaystyle {}^{}}$/ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle E}$) ${\displaystyle O(\min\{V^{2/3},E^{1/2}\}E)}$번으로$$ 실행된다.^[6]

초당적 일치 문제에서 발생하는 네트워크에서는 위상 $수$가 O$){\displaystyle$ O$({\sqrt{V}})$로 제한되므로$$$){\displaystyle O({\sqrt{V}E)}$ 시간$$ 바인딩으로 이어진다.결과 알고리즘은 Hopcroft-Karp 알고리즘으로도 알려져 있다.보다 일반적으로, 이 바운드는 모든 단위 네트워크에 대해 유지된다. 즉, 소스와 싱크를 제외한 각 꼭지점이 하나의 입력 용량 에지 또는 하나의 송신 용량 에지 중 하나를 갖는 네트워크, 그리고 다른 모든 용량은 임의의 정수다.^[4]

예

다음은 다이닉의 알고리즘 시뮬레이션이다.레벨 그래프 $G{\displaystyle {}_{}}$ ${\displaystyle L_{}}$ ${\$에서 라벨이 빨간색으로 표시된 정점은${\displaystyle }$값 ${\displaystyle \mathrm{distred}}$($){\displaystyle \operatorname {dist}$ ($v)}$ 입니다$.$파란색으로 표시된 경로는 차단 흐름을 형성한다.

	$(\displaystyle G}$	${\displaystyle G_{f}}$	${\displaystyle G_{L}}$
1.
	차단 흐름은 다음과 같이 구성된다. ${\displaystyle \mathrm{흐름}}$의 4단위가 있는$$${\displaystyle }${${\displaystyle \mathrm{s},}$ 1,${\displaystyle }$3,$}$ {\$displaystyle \{s,1$,3,t$\}}$ ${\displaystyle \mathrm{흐름}}$ 6단위의 {s$$${\displaystyle ,}$ ${\displaystyle 1}$,${\displaystyle 4}$,${\displaystyle t}$ ${\displaystyle \}}$ ${\displaystyle \{s,1,4,t\}}$ ${\displaystyle \mathrm{흐름}}$ 4단위의 {s$$${\displaystyle ,2}$,${\displaystyle 4}$,${\displaystyle t}$ ${\displaystyle \}}$ ${\displaystyle \{s,2,4,t\}}.$ 따라서 차단 유량은 14단위, flow ${\displaystyle f}$ $displaystyle$f$}$의 값은 14이다$$.블럭화 흐름의 각 증강 경로에는 3개의 가장자리가 있다는 점에 유의하십시오.
2.
	차단 흐름은 다음과 같이 구성된다. ${\displaystyle }$흐름 5단위의${\displaystyle }${${\displaystyle s,}$ ${\displaystyle 2}$, ${\displaystyle 4}$,${\displaystyle 3}$,${\displaystyle t}$ ${\displaystyle \}}$ ${\displaystyle \{s,2,4,3,t\}}.$ 따라서 차단 유량은 5단위로 ${\displaystyle flow}$ f $displaystyle$f$}$의 값은 14 + 5 = 19이다$$.각 증강 경로에는 4개의 가장자리가 있다는 점에 유의하십시오.
3.
	${\displaystyle t_{}}$ ${\displaystyle t}$은(는) $G{\displaystyle {}_{}}$ f ${\$에서 도달할 수 없으므로$$ 알고리즘은 종료되고 최대값 19의 흐름을 반환한다$.$각 블럭 흐름에서 증가 경로의 에지 수가 최소 1개씩 증가한다는 점에 유의하십시오.

참고 항목

• 포드-풀커슨 알고리즘
• 최대 흐름 문제

메모들

참조

• Yefim Dinitz (2006). "Dinitz' Algorithm: The Original Version and Even's Version" (PDF). In Oded Goldreich; Arnold L. Rosenberg; Alan L. Selman (eds.). Theoretical Computer Science: Essays in Memory of Shimon Even. Springer. pp. 218–240. ISBN 978-3-540-32880-3.
• Tarjan, R. E. (1983). Data structures and network algorithms.
• B. H. Korte; Jens Vygen (2008). "8.4 Blocking Flows and Fujishige's Algorithm". Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. pp. 174–176. ISBN 978-3-540-71844-4.