Dinits algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 maj 2021; kontroller kräver 3 redigeringar .

Dinitz-algoritmen är en polynomalgoritm för att hitta det maximala flödet i ett transportnätverk , föreslog 1970 av den sovjetiske (senare israeliska) matematikern Efim Dinitz . Algoritmens tidskomplexitet är . En sådan uppskattning kan erhållas genom att introducera begreppen ett hjälpnätverk och ett blockerande (pseudomaximalt) flöde . I nätverk med enhetsbandbredd finns det en starkare tidskomplexitetsuppskattning: . $O(|V|^{2}|E|)$ $O(|E||V|)$

Beskrivning

Låta vara ett transportnät , där och är respektive genomströmningen och flödet genom kanten . $G=(V,E,c,s,t)$ $c(u,v)$ $f(u,v)$ $(u,v)$

Den återstående bandbredden är en mappning som definieras som:

{\displaystyle c_{f}\colon V\times V\to \mathbb {R} ^{+))

Om , $(u,v)\in E$ $c_{f}(u,v)=c(u,v)-f(u,v)$ $c_{f}(v,u)=f(u,v)$ I andra källor $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$
$c_{f}(u,v)=0$ annat.

Restnätverk - graf , var

G_{f}=(V,E_{f},c_{f}|_{E_{f)),s,t)

{\displaystyle E_{f}=\{(u,v)\in V\times V\mid c_{f}(u,v)>0\))

. En komplementär väg är en väg i restgrafen .

st

G_f

Låt vara längden på den kortaste vägen från till i grafen . Då är grafens hjälpnätverk grafen , där

\operatörsnamn {avstånd} (v)

s

v

G_f

G_f

G_{L}=(V,E_{L},c_{f}|_{E_{L)),s,t)

{\displaystyle E_{L}=\{(u,v)\in E_{f}\mid \operatorname {dist} (v)=\operatorname {dist} (u)+1\))

. Ett blockerande flöde är ett flöde så att graf c inte innehåller en väg.

st

f

G'=(V,E_{L}',c_{f}|_{E_{L)),s,t)

E_{L}'=\{(u,v)\mid f(u,v)<c_{f}|_{E_{L}}(u,v)\}

st

Algoritm

Dinits algoritm

Ingång : Nätverk .

G=(V,E,c,s,t)

Effekt : maximalt flöde .

st

f

Installera för varje . $f(e)=0$ $e\in E$
Skapa från graf . Om , stoppa och mata ut . $G_L$ $G_f$ $G$ $\operatörsnamn {avstånd} (t)=\infty$ $f$
Hitta blockerande tråd i . $f'$ $G_L$
Förstärk flödet med flödet och gå till steg 2. $f$ $f'$

Analys

Det kan visas att varje gång antalet kanter på den kortaste vägen från källan till sänkan ökar med minst en, så det finns inga fler blockerande flöden i algoritmen, där är antalet hörn i nätverket. Det extra nätverket kan byggas genom bredd-först genomgång i tid , och det blockerande flödet på varje nivå i grafen kan hittas i tid . Därför är körtiden för Dinits-algoritmen . $n-1$ $n$ $G_L$ $O(|V|+|E|)$ $O(|V||E|)$ $O(|V|)\cdot (O(|V|+|E|)+O(|V||E|))=O(|V|^{2}|E|)$

Med hjälp av datastrukturer som kallas dynamiska träd är det möjligt att hitta blockeringsflödet på varje fas i tiden , sedan kan körtiden för Dinitz algoritm förbättras till . $O(|E|\log |V|)$ $O(|V||E|\log |V|)$

Exempel

Nedan är en simulering av Dinitz algoritm. I det extra nätverket är hörnen med röda etiketter värdena . Den blockerande tråden är markerad med blått. $G_L$ $\operatörsnamn {avstånd} (v)$

	$G$	$G_f$	$G_L$
ett.
	En blockerande tråd består av banor: $\{s,1,3,t\}$ med 4 flödesenheter, $\{s,1,4,t\}$ med 6 flödesenheter, och ${\displaystyle \{s,2,4,t\))$ med 4 flödesenheter. Därför innehåller det blockerande flödet 14 enheter, och flödesvärdet är 14. Observera att den komplementära banan har 3 kanter. $\|f\|$
2.
	En blockerande tråd består av banor: ${\displaystyle \{s,2,4,3,t\))$ med 5 flödesenheter. Därför innehåller det blockerande flödet 5 enheter, och flödets värde är 14 + 5 = 19. Observera att den komplementära banan har 4 kanter. $\|f\|$
3.
	Aktien är inte tillgänglig på nätverket . Därför stoppar algoritmen och returnerar det maximala flödet av storleken 19. Observera att i varje blockerande flöde ökas antalet kanter i den komplementära banan med minst en. $t$ $G_f$

Historik

Dinitz-algoritmen publicerades 1970 av den före detta sovjetiske vetenskapsmannen Efim Dinitz, som nu är medlem av fakulteten för datateknik vid Ben-Gurion University (Israel), tidigare än Edmonds-Karp-algoritmen , som publicerades 1972, men skapat tidigare. De visade oberoende att i Ford-Fulkerson-algoritmen , om den komplementära vägen är den kortaste, minskar inte längden på den komplementära vägen.

Dinitzs algoritm med förökning

Algoritmens tidskomplexitet kan reduceras genom att optimera processen för att hitta en blockerande tråd. För att göra detta är det nödvändigt att introducera begreppet potential . Kantpotentialen är , och vertexpotentialen är . Enligt samma logik , en . Tanken med förbättringen är att leta efter en vertex med minsta positiva potential i hjälpnätverket och bygga ett blockerande flöde genom det med hjälp av köer . $e\in E$ $\operatorname {pot} (e)=c_{f}(e)$ ${\displaystyle v\in V\setminus \{s,t\))$ $\operatorname {pot} (v)=\min\{\sum _{e\in \delta ^{+}(v)}\operatörsnamn {pot} (e),\summa _{e\in \ delta ^{-}(v)}\operatörsnamn {pot} (e)\}$ $\operatörsnamn {pot} (s)=\summa _{e\in \delta ^{+}(v)}\operatörsnamn {pot} (e)$ $\operatörsnamn {pot} (t)=\summa _{e\in \delta ^{-}(v)}\operatörsnamn {pot} (e)$

Ingång : Nätverk .

G=(V,E,c,s,t)

Effekt : maximalt flöde .

st

f

Installera för varje . $f(e)=0$ $e\in E$
Skapa från graf . Om , stoppa och mata ut . $G_L$ $G_f$ $G$ $\operatörsnamn {avstånd} (s,t)=\infty$ $f$
Installera för varje . $f'(e)=0$ $e\in E$
Bestäm potentialen för varje vertex.
Så länge det finns en vertex sådan att : $v\in V$ $\operatorname {pot} (v)>0$
1. Definiera flödet med hjälp av framåtriktad utbredning från . $f''$ $v$
2. Bestäm flödet med hjälp av backpropagation från . $f'''$ $v$
3. Komplettera streamen med streams och . $f'$ $f''$ $f'''$
Förstärk flödet med flödet och gå till steg 2. $f$ $f'$

Algoritmer för framåt- och bakåtpropagation tjänar till att hitta vägar från till respektive från till . Ett exempel på den direkta spridningsalgoritmen som använder köer: $v$ $t$ $s$ $v$

Ingång : Hjälpnätverk , vertex sådan att .

G_{L}=(V,E_{L},c_{f}|_{E_{L)),s,t)

v\in V

\operatorname {pot} (v)>0

Output : Ett flöde från källa till vertex som är en del av ett blockerande flöde.

f''

s

v

Installera för alla : . ${\displaystyle w\in V\setminus \{v\))$ $U(w)=0$
Installera och . $U(v)=\operatörsnamn {pot} (v)$ $\operatörsnamn {pot} (v)=0$
Lägg till i kö . $v$ $F$
Så länge kön inte är tom: $F$
1. Ställ in värdet på det sista elementet i kön. $v$
2. Hejdå : $U(v)>0$
  1. För varje kant : $e=(v,w)\in \delta ^{+}(v)$
  2. ${\displaystyle f''(e)=\min\{\operatörsnamn {pot} (e),U(v)\))$ .
  3. Uppdatering . $U(v)=U(v)-f''(e)$
  4. Uppdatering . $U(w)=U(w)+f''(e)$
  5. Installera . $\operatörsnamn {pot} (w)=\operatörsnamn {pot} (w)-\operatörsnamn {pot} (e)$
  6. Om och avkö . _ $w\neq t$ $U(w)=f''(e)$ $w$ $F$

På grund av det faktum att minst en vertex är "mättad" i varje iteration av sökningen efter ett blockerande flöde, slutförs det i värsta fall iterationer, som var och en tar hänsyn till maximalt antal hörn. Låt vara antalet "mättade" kanter i varje -te iteration av sökningen efter en blockerande tråd. Då är dess asymptotiska komplexitet , där är antalet hörn och är antalet kanter i grafen. Således är den asymptotiska komplexiteten hos Dinitz spridningsalgoritm lika med , eftersom det blockerande flödet som mest kan passera genom hörn. $|V|-1$ $|V|$ $l_{i}$ $i$ $\sum _{i=1}^{n-1}O(n+l_{i})=O(n^{2}+\summa _{i=1}^{n-1}l_ {i})=O(n^{2}+m)$ $n$ $m$ $O(|V|^{3})$ $|V|$

Litteratur

Yefim Dinitz. Dinitz algoritm: Originalversionen och Evens version // Teoretisk datavetenskap: Essays in Memory of Shimon Even (engelska) / Oded Goldreich, Arnold L. Rosenberg och Alan L. Selman. - Springer, 2006. - S. 218-240. — ISBN 978-3540328803 .
BH Korte, Jens Vygen. 8.4 Blockering av flöden och Fujishiges algoritm // Kombinatorisk optimering: teori och algoritmer (Algorithms and Combinatorics, 21 ) . - Springer Berlin Heidelberg , 2008. - P. 174-176 . — ISBN 978-3-540-71844-4 .

Länkar

Dinits algoritm på e-maxx.ru: Beskrivning, bevis, implementering i C++