Диницов алгоритам

Диницов алгоритам је строго полиномијални алгоритам за израчунавање максималног протока кроз транспортну мрежу осмишљен 1970. године од стране израелског (претходно совјетског) изучивача компјутера Јефим Динитз [1][1] алгоритам се извршава у временском периоду О(В²Е) и сличан је Емонд-Карп Алгоритму који се извршава у времену О(ВЕ²) у томе да користи најкраће промењене путање. Увод концепта о графа са нивоима и блокирања тока омогућују Диницовом алгоритму да постигне своје извођење.

Историја[уреди | уреди извор]

Динитц алгоритам је 1970. године објавио бивши руски изучивач компјутера Јефим А. Динитц, који је данас члан Одсека за науку рачунарства нa Бен-Гурион Универзитету Негав (Израел), пре Едмондс-карп алгоритма који је објављен 1972. године али је раније откривен. Независно су показали да у Форд-фулкерсон алгоритму [2][2] ако је свака промењљива путања најкраћа, онда дужина променљивих путања не опада.

Дефиниција[уреди | уреди извор]

Нека је $G=((V,E),c,s,t)$ мрежа са $c(u,v)$ и $f(u,v)$ тежина и проток грана $(u,v)$ (у том редоследу).

Преостала тежина је Сликање

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

дефинисано као

1. ако

(u,v)\in E

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

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

2. иначе

c_{f}(u,v)=0

Преостали граф

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

где:

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

Промењљива путања је

s-t

путања у преосталом графу

G_{f}

.

дефинишемо дист(в) да буде дужина накраће путање од с до в у графу

G_{f}

. Онда граф са нивоима

G_{f}

је граф

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

где:

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

Блокирајући ток је

s-t

ток

f

такав да граф

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

са

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

не садржи

s-t

путању

Алгоритам[уреди | уреди извор]

Диницов алгоритам

Улаз граф

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

Излаз:

s-t

ток

f

максималне вредности

иницијализујемо $f(e)=0$ за свако $e\in E$
Конструишемо $G_{L}$ уз помоћ $G_{f}$ од $G$ . Ако је $\operatorname {dist} (t)=\infty$ стани и стави $f$ на излаз.
Нађемо блокирајући ток $f\;'$ у $G_{L}$
Ускладимо $\ f$ успомоћ $f\;'$ и вратимо се на други корак

Анализа алгоритма[уреди | уреди извор]

Може бити показано да се број грана у сваком блокирајућем току повећава за барем 1 сваки пут тако да има највише $n-1$ блокирајућих токова у алгоритму, где је $n$ број чворова у графу. Граф са нивоима $G_{L}$ може бити конструисан претрагом у ширину у $O(E)$ времену а блокирајући ток у сваком нивоу графа се може пронаћи у $O(VE)$ времену. Дакле Време извршавања овог алгоритма је $O(V^{2}E)$ .

Користећи структуру података звану динамичко дрве време потребно за налажење блокирајућег тока се може смањити на $O(E\log V)$ , па се време извршавања овог алгоритма може побољшати на $O(VE\log V)$ .

Специјални случајеви[уреди | уреди извор]

У графу са јединичним тежинама, постоји много јача временска граница. Сваки блокирајући ток се може наћи за $O(E)$ и може се показати да број фаза не прелази $O({\sqrt {E}})$ и $O(V^{2/3})$ . Тако да се алгоритам извршава у $O(\min\{V^{2/3},E^{1/2}\}E)$ времену^[3].

У графовима насталим током решавања проблема бипартитивног упаривања број фаза је ограничен са $O({\sqrt {V}})$ , одтле водећи временску границу $O({\sqrt {V}}E)$ . Резултујући алгоритам је познат као Хопцртфт-Карп алгоритам. Генералније ова граница држи било који граф -- граф у којем сваки чвор осим извора и понора има или једну улазну грану тежине један или једну излазну грану тежине један, а све остале тежине су произвољни цели бројеви.^[4]

Пример[уреди | уреди извор]

Следеће је симулација динитц алгоритма. У гафу са нивоима $G_{L}$ чворови у црвеној боји су вредности $\operatorname {dist} (v)$ . Путање плаве боје су блокирајући ток.

	$G$	$G_{f}$	$G_{L}$
1.
	Блокирајући ток се састоји од $\{s,1,3,t\}$ са 4 јединице тока $\{s,1,4,t\}$ са 6 јединице тока $\{s,2,4,t\}$ ца 4 јединице тока Дакле блокирајући ток је састављен од 14 јединица тока , и вредност тока $\|f\|$ је 14. приметити да свака промењљива путања у блокирајућем току има 3 гране.
2.
	Блокирајући ток се састоји од $\{s,2,4,3,t\}$ са 5 јединица тока. Дакле блокирајући ток се састоји од 5 јединица и вредност тока $\|f\|$ је 14+5=19. Приметити да свака промењљива путања има 4 гране.
3.
	Пошто $t$ не може да се достигне у $G_{f}$ алгоротам завршава са радом и враћаток са максималном вредношћу 19. Приметити да у сваком блокирајућем току број грана у промењљивим путањама се повећава за барем 1.