Dinicov algoritam

Dinicov algoritam je strogo polinomijalni algoritam za izračunavanje maksimalnog protoka kroz transportnu mrežu osmišljen 1970. godine od strane izraelskog (prethodno sovjetskog) izučivača kompjutera Jefim Dinitz [1][1] algoritam se izvršava u vremenskom periodu O(V²E) i sličan je Emond-Karp Algoritmu koji se izvršava u vremenu O(VE²) u tome da koristi najkraće promenjene putanje. Uvod koncepta o grafa sa nivoima i blokiranja toka omogućuju Dinicovom algoritmu da postigne svoje izvođenje.

Istorija

Dinitc algoritam je 1970. godine objavio bivši ruski izučivač kompjutera Jefim A. Dinitc, koji je danas član Odseka za nauku računarstva na Ben-Gurion Univerzitetu Negav (Izrael), pre Edmonds-karp algoritma koji je objavljen 1972. godine ali je ranije otkriven. Nezavisno su pokazali da u Ford-fulkerson algoritmu [2][2] ako je svaka promenjljiva putanja najkraća, onda dužina promenljivih putanja ne opada.

Definicija

Neka je $G=((V,E),c,s,t)$ mreža sa $c(u,v)$ i $f(u,v)$ težina i protok grana $(u,v)$ (u tom redosledu).

Preostala težina je Slikanje

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

definisano kao

1. ako

(u,v)\in E

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

c_{f}(v,u)=f(u,v)

2. inače

c_{f}(u,v)=0

Preostali graf

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

gde:

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

Promenjljiva putanja je

s-t

putanja u preostalom grafu

G_{f}

.

definišemo dist(v) da bude dužina nakraće putanje od s do v u grafu

G_{f}

. Onda graf sa nivoima

G_{f}

je graf

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

gde:

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

Blokirajući tok je

s-t

tok

f

takav da graf

G'=(V,E_{L}',s,t)

sa

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

ne sadrži

s-t

putanju

Algoritam

Dinicov algoritam

Ulaz graf

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

Izlaz:

s-t

tok

f

maksimalne vrednosti

inicijalizujemo $f(e)=0$ za svako $e\in E$
Konstruišemo $G_{L}$ uz pomoć $G_{f}$ od $G$ . Ako je $\operatorname {dist} (t)=\infty$ stani i stavi $f$ na izlaz.
Nađemo blokirajući tok $f\;'$ u $G_{L}$
Uskladimo $\ f$ uspomoć $f\;'$ i vratimo se na drugi korak

Analiza algoritma

Može biti pokazano da se broj grana u svakom blokirajućem toku povećava za barem 1 svaki put tako da ima najviše $n-1$ blokirajućih tokova u algoritmu, gde je $n$ broj čvorova u grafu. Graf sa nivoima $G_{L}$ može biti konstruisan pretragom u širinu u $O(E)$ vremenu a blokirajući tok u svakom nivou grafa se može pronaći u $O(VE)$ vremenu. Dakle Vreme izvršavanja ovog algoritma je $O(V^{2}E)$ .

Koristeći strukturu podataka zvanu dinamičko drve vreme potrebno za nalaženje blokirajućeg toka se može smanjiti na $O(E\log V)$ , pa se vreme izvršavanja ovog algoritma može poboljšati na $O(VE\log V)$ .

Specijalni slučajevi

U grafu sa jediničnim težinama, postoji mnogo jača vremenska granica. Svaki blokirajući tok se može naći za $O(E)$ i može se pokazati da broj faza ne prelazi $O({\sqrt {E}})$ i $O(V^{2/3})$ . Tako da se algoritam izvršava u $O(\min\{V^{2/3},E^{1/2}\}E)$ vremenu^[3].

U grafovima nastalim tokom rešavanja problema bipartitivnog uparivanja broj faza je ograničen sa $O({\sqrt {V}})$ , odtle vodeći vremensku granicu $O({\sqrt {V}}E)$ . Rezultujući algoritam je poznat kao Hopcrtft-Karp algoritam. Generalnije ova granica drži bilo koji graf -- graf u kojem svaki čvor osim izvora i ponora ima ili jednu ulaznu granu težine jedan ili jednu izlaznu granu težine jedan, a sve ostale težine su proizvoljni celi brojevi.^[4]

Primer

Sledeće je simulacija dinitc algoritma. U gafu sa nivoima $G_{L}$ čvorovi u crvenoj boji su vrednosti $\operatorname {dist} (v)$ . Putanje plave boje su blokirajući tok.

	$G$	$G_{f}$	$G_{L}$
1.
	Blokirajući tok se sastoji od $\{s,1,3,t\}$ sa 4 jedinice toka $\{s,1,4,t\}$ sa 6 jedinice toka $\{s,2,4,t\}$ ca 4 jedinice toka Dakle blokirajući tok je sastavljen od 14 jedinica toka , i vrednost toka $\|f\|$ je 14. primetiti da svaka promenjljiva putanja u blokirajućem toku ima 3 grane.
2.
	Blokirajući tok se sastoji od $\{s,2,4,3,t\}$ sa 5 jedinica toka. Dakle blokirajući tok se sastoji od 5 jedinica i vrednost toka $\|f\|$ je 14+5=19. Primetiti da svaka promenjljiva putanja ima 4 grane.
3.
	Pošto $t$ ne može da se dostigne u $G_{f}$ algorotam završava sa radom i vraćatok sa maksimalnom vrednošću 19. Primetiti da u svakom blokirajućem toku broj grana u promenjljivim putanjama se povećava za barem 1.