Pokud budeme ve Ford-Fulkersonově algoritmu volit nejkratší vylepšující cestu (s nejmenším počtem hran), tak se dramaticky zlepší časová složitost celého algoritmu.

Tento nápad uvedli ve své práci už Ford a Fulkerson, ale popsali ho jako heuristiku. Jako první provedl analýzu této heuristiky ruský matematik Dinits (často překládán jako Dinic) v roce 1970. Edmonds a Karp nezávisle publikovali slabší analýzu v roce 1972. Ale protože to byla první anglicky publikovaná analýza, tak se algoritmus často označuje jako Edmonds-Karpův. Dinic navíc přišel s vrstevnatou (čistou) sítí a blokujícím tokem a pomocí něj ukázal rychlejší implementaci algoritmu. Proto budeme algoritmus označovat jako Dinicův.

Ve skutečnosti je stejně těžké najít vylepšující cestu jako najít nejkratší vylepšující cestu. Oboje můžeme řešit průchodem do šířky. Proto je vylepšení algoritmu tak jednoduchou modifikací, že bychom ji ve Ford-Fulkersonově algoritmu použili, aniž bychom o tom věděli.

Nejprve si ukážeme, jak jednoduše hledat nejkratší vylepšující cestu.


Původní síť $G$

1) Máme síť s grafem $G$ a tokem $f$ ( původní síť). Pro zjednodušení výkladu předpokládejme, že v $G$ ke každé hraně $uv$ existuje opačná hrana $vu$. Pokud ne, tak do $G$ přidáme hranu $vu$ s nulovou kapacitou. Toto rozšíření grafu $G$ nijak nezmění aktuální, ani maximální tok, ale zjednoduší se zavedení a práci s rezervou hrany.

2) Chceme vytvořit pomocnou síť, která nám zjednoduší hledání vylepšující cesty. Nechceme se dívat na hrany v protisměru, ani nechceme, aby v síti existovaly násobné orientované hrany. Tuto síť vytvoříme na základě původní sítě a toku $f$. Nazveme ji síť rezerv $G_f$.

Síť rezerv $G_f$

Rezerva $r(uv)$ říká, jak velký tok protlačíme z $u$ do $v$, a odpovídá součtu rezervy hrany $uv$ po směru a rezervy hrany $vu$ v protisměru. Spočítá se jako $$r(uv)=(c(uv)-f(uv))+f(vu).$$ Do sítě rezerv dáme jen ty hrany (rozšířené) původní sítě, které mají nenulovou rezervu, a ohodnotíme je rezervou. Každá orientovaná cesta v síti rezerv odpovídá vylepšující cestě v původní síti.

Čistá síť $G^*_f$

3) Na základě sítě rezerv vytvoříme čistou síť $G^*_f$. Do čisté sítě dáme jen ty hrany sítě rezerv, které leží na nejkratší cestě ze zdroje do spotřebiče. Můžeme ji zkonstruovat pomocí průchodu do šířky, který rozdělí vrcholy do vrstev podle vzdálenosti od zdroje. Proto se této síti někdy říká vrstevnatá síť.

Hrana $e$ původní sítě je nasycená vzhledem k toku $f$, pokud $r(e)=0$ (hranou $e=uv$ i opačnou hranou $vu$ v protisměru protéká největší možný tok směrem z $u$ do $v$). Orientovaná cesta je nasycená, pokud obsahuje nasycenou hranu. Nasycená cesta je tedy opakem vylepšující cesty.

Analýza Dinicova/Edmonds-Karpova algoritmu

Délkou orientované cesty myslíme počet hran na cestě. Vzdálenost z vrcholu $x$ do vrcholu $y$ je délka nejkratší orientované cesty z $x$ do $y$ v síti rezerv $G_f$. Označíme ji $d_f(x,y)$. Pro cesty vedoucí ze zdroje $s$ píšeme zkráceně $d_f(y)$ místo $d_f(s,y)$.

Klíčové lemma říká, že po vylepšení toku podél nejkratší vylepšující $(s,t)$-cesty neklesne v síti rezerv délka nejkratší cesty ze zdroje do spotřebiče.

Vylepšením toku podél vylepšující cesty se některé hrany nasytí. Jejich rezerva klesne na nulu a proto zmizí ze sítě rezerv. Tím délka nejkratší cesty v $G_f$ určitě neklesne.

Na druhou stranu se v síti rezerv mohou objevit nové hrany. Jsou to hrany, které měly nulovou rezervu, ale při vylepšení toku jsme po opačné hraně poslali nenulový tok. Každá nová hrana vede z $i$-té vrstvy čisté sítě do $(i-1)$-ní (pro nějaké $i$). Každá $(s,t)$-cesta používající alespoň jednu novou hranu, musí alespoň jednou skočit o vrstvu zpět, ale nikdy nemůže skočit více než o jednu vrstvu dopředu. Proto je nová cesta alespoň o $2$ delší, než byla délka cesty, podle které jsme vylepšovali tok.

Lemma zformulujeme malinko obecněji a ukážeme, že po vylepšení neklesne žádná vzdálenost ze zdroje $s$ do libovolného vrcholu $v$.

Lemma: Nechť $f$ je tok a $f’$ je tok, který vznikne vylepšením $f$ podél nejkratší vylepšující cesty $P$. Potom pro každý vrchol $v\in V$ platí $d_{f‘}(v)\geq
d_f(v)$.
Důkaz: Označme vrcholy na nejkratší vylepšující cestě $P$ v síti $G_f$ jako $s=v_0$, $v_1$, \dots, $v_k=t$. Předpokládejme pro spor, že existuje vrchol $v$ takový, že $d_{f‘}(v) \lt d_f(v)$. Ze všech takových vrcholů si vybereme ten s nejmenším $d_{f‘}(v)$. Určitě platí $v\not = s$. Nechť $w$ je předposlední vrchol na nejkratší cestě do $v$ v síti $G_{f‘}$, potom $d_{f‘}(v) = d_{f‘}(w)+1$. Z volby vrcholu $v$ platí $d_{f}(w) \leq d_{f‘}(w)$.

Hrana $wv$ se musela v grafu objevit až po vylepšení, jinak bychom průchodem po hraně $wv$ v síti $G_f$ dostali $d_{f}(v) \leq d_f(w)+1 \leq d_{f‘}(w)+1 \leq d_{f‘}(v)$. Proto je $wv$ opačnou hranou k hraně $v_{i-1} v_{i}$ na cestě $P$, pro nějaké $i$. Potom je $d_{f}(w)=i$ a $d_{f}(v)=i-1$. Na druhou stranu je $d_{f‘}(v)\geq d_{f‘}(w)+1 \geq i+1$. To je spor.

Následující lemma říká, že pokud po vylepšení toku podél nejkratší vylepšující $(s,t)$-cesty nevzroste délka nejkratší $(s,t)$-cesty, bude nová čistá síť podgrafem původní čisté sítě. Proto stačí aktualizovat původní čistou síť a nemusíme ji po každém vylepšení počítat znova.

Lemma: Nechť $f$ je tok a $f’$ je tok, který vznikne vylepšením $f$ podél nejkratší vylepšující cesty. Pokud $d_{f}(t)=d_{f‘}(t)$, tak $G^*_{f‘} \subseteq G^*_f$.
Důkaz: Čistá sít obsahuje právě hrany ležící na nejkratší cestě ze zdroje do spotřebiče. Nechť $k:=d_{f}(t)$.

Během vylepšování toku podél cesty se mohou objevit nové hrany. Z předchozího důkazu ale vyplývá, že každá cesta ze zdroje do spotřebiče používající novou hranu je alespoň o dva delší než $k$. Proto se žádná nová hrana nemůže objevit v čisté síti a tedy čistá síť $G^*_{f‘}$ je podgrafem předchozí čisté sítě $G^*_{f}$.

Lemma: Dinicův/Edmonds-Karpův algoritmus provede vylepšení podél nejvýše $mn$ vylepšujících cest.
Důkaz: Délka nejkratší vylepšující cesty v průběhu algoritmu neklesá. Proto můžeme běh algoritmu rozdělit do fází podle délky nejkratší vylepšující cesty. Fází je nejvýše tolik, kolik je různých délek cest a to je nejvýše $n$. Podle lemma [ref]lemma_cista_sit[/ref] do čisté sítě během fáze nepřibudou žádné hrany. V každé fázi provedeme nejvýše $m$ vylepšení, protože se při každém vylepšení nasytí aspoň jedna hrana a zmizí z čisté sítě.