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

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

Историја

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

Дефиниција

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

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

c_{f} : 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} : dist (v) = 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$ . Ако је $dist (t) = \infty$ стани и стави $f$ на излаз.
Нађемо блокирајући ток $f^{'}$ у $G_{L}$
Ускладимо $f$ успомоћ $f^{'}$ и вратимо се на други корак

Анализа алгоритма

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

Користећи структуру података звану динамичко дрве време потребно за налажење блокирајућег тока се може смањити на $O (E \log V)$ , па се време извршавања овог алгоритма може побољшати на $O (V E \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}$ чворови у црвеној боји су вредности $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.