Fordův–Fulkersonův algoritmus

Příklad průběhu Ford-Fulkersonova algoritmu

Fordův-Fulkersonův algoritmus (pojmenovaný podle L. R. Forda, Jr. a D. R. Fulkersona) počítá maximální tok v síti. Název Ford-Fulkerson je také často používán pro Edmondsův-Karpův algoritmus, který je specializací Fordova-Fulkersonova algoritmu.

Myšlenka algoritmu je velmi jednoduchá: Dokud existuje cesta ze zdroje (výchozí bod) do spotřebiče (koncový bod), taková, že je možnost ještě zvětšit její tok, neboli, že každá hrana na této cestě muže ještě „propustit“ vyšší tok (není ve stavu saturace), tak na všech hranách této cesty zvýšíme tok o největší hodnotu, o kterou lze zvětšit tok ve všech hranách cesty. Poté celý postup opakujeme. Cesta s volnou kapacitou se nazývá zlepšující cesta.

Obecná teorie k algoritmu

Velikost toku nikdy nepřekročí kapacitu žádného řezu sítě. Toto tvrzení pouze naznačuje, že sítí není možno „protlačit“ vyšší tok než je maximální kapacita řezu sítě (toto je obsaženo v upozornění, že se to týká všech řezů sítě, tzn. i minimálního s jeho „maximální“ kapacitou).

Pro orientovaný graf $G$ s množinou hran $E$ a množinou vrcholů $V$, funkci $q$ určující kapacitu hran, vrcholy $s$ a $t$ grafu $G$, kde $s$ je zdroj a $t$ spotřebič platí: Tvrzení „tok $f$ je maximálním tokem v síti $S=\langle G,q,s,t\rangle$“ je ekvivalentní s tvrzením že neexistuje neorientovaná cesta $P=\langle u_{0},u_{1},\ldots ,u_{n}\rangle$, $u_{0}=s$, $u_{n}=t$ taková, že pro každou dvojici $[u_{i},u_{i+1}]$ platí:

• $f[u_{i},u_{i+1}]<q[u_{i},u_{i+1}]$, pokud hrana $[u_{i},u_{i+1}]$ náleží $E(P)$
• $f[u_{i+1},u_{i}]>0$, pokud hrana $[u_{i+1},u_{i}]$ náleží $E(P)$

Taková P by se nazývala zlepšující cestou.

Obecná implementace v pseudokódu

Ford-Fulkerson (S)
 for ( Edge (u,v) in E(G) )
  f(u,v) = 0; 
 while ( NajdiCestu(S) )
  ZvyšTok(S);
 return f;

Obecný popis implementace metod

boolean NajdiCestu(Node s) {
 for ( Node u in V(G) )
  stav[u] = FRESH;
 p[s] = +s;
 d[s] = ∞;
 stav[s] = OPEN;
 do  { 
  u = libovolný otevřený uzel;
  stav[u] = CLOSED;
  for (Node v in Nasl(u)) {
   if ((stav[v] == FRESH) && (f(u,v) < q(u,v))) { 
    stav[v] = OPEN;
    p[v] = +u;
    d[v] = min(d[u], q(u,v) – f(u,v));    
   } 
  }
  for (Node v in předch(u)) {
   if (stav[v] == FRESH) && (f(v,u) > 0)) { 
    stav[v] = OPEN;
    p[v] = -u;
    d[v] = min(d[u], f(v,u));
   }
  } 
 } while ((existuje otevřený uzel)  && (u != t));
 return (u == t);
}

void ZvyšTok(Node s) {
 x = t;
 delta = d[t];
 do {
  v = x;
  sgn = p[v];
  u = abs(sgn);
  if (sgn > 0)
   f(u,v) += delta;
  else
   f(v,u) -= delta;
  x = u;
 } while ( v != s );
}

Vysvětlení algoritmu

Tento algoritmus začíná tak, že všem hranám přiřadí tok hodnoty nula, neboli nic sítí na počátku neprotéká. Dále pak začne testovat nalezení zlepšující cesty, jestliže tato cesta bude nalezena tak se tok zvýší. Naopak jestliže cesta nalezená už nebude, to znamená že zlepšující cesta už neexistuje (viz obecná teorie k algoritmu) je nalezen maximální tok.

Funkce NajdiCestu(S) na počátku své implementace přiřadí všem uzlům grafu jako stav uzlu hodnotu FRESH. To znamená, že tyto uzly jsou čisté neboli ještě nepoužité. Uzlu S se přiřadí p[s] směr kterým jde hrana a poté ještě delta s jako nekonečno jelikož je to uzel předaný parametrem a tento uzel se otevře. Poté startuje cyklus který na svém začátku vybere uzel který je otevřený (stav uzlu == otevřeno ) a uzavře ho a poté pro všechny jeho následníky zjistí že jestliže je následník, uzel fresh a jeho tok je nižší než kapacita hrany jež spojuje uzel s tímto následníkem, tak ho otevře, přiřadí mu směr kterým je orientovaná hrana a vypočte pro něj delta. Delta se vypočítává právě pro to aby bylo možné zjistit o kolik se dá navýšit tok v hranách orientovaných směrem od zdroje k spotřebiči a snížit tok na hraně směřující od spotřebiče ke zdroji (bilance zůstává stejná). Když se takto projedou všechny následovníci tak se začnou procházet všichni předchůdci tohoto uzlu. U nich se zjišťuje zda jsou FRESH a zda hrana spojující tyto dva uzly má vyšší tok než nula. Když je tato podmínka splněna nastaví se předchůdce na stav OPEN nastaví se mu orientace hrany a určí delta. A toto celé se opakuje dokud existuje alespoň nějaký otevřený uzel či dokud testovaný uzel u se nebude rovnat spotřebiči. A také na základě této naposledy zmiňované rovnosti bude funkce vracet návratovou hodnotu true nebo false.

Odpověď na otázku jak je možné, že tok může "téci" i proti směru orientace hrany v síti?

Vysvětleme si to například na vodovodním potrubí. Existuje jedna trubka, která bude mít orientaci proti směru vodovodu to znamená od domácnosti do vodárny. Jak je možné, že by touto trubkou tekla voda proti její orientaci? Fyzicky to možné není, ale hodnota jejího toku tomu může ukazovat. Tuto hodnotu trubka má jen proto, že jestliže my potřebujeme touto opačně orientovanou trubkou poslat například 3 litry směrem vodárna→ domácnost, tak jestliže například 10 litru vody jí proteče ve směru domácnost→vodárna, tak ona svůj průtok zmenši třeba na 7 litrů a ty tři litry nechá protéct někde jinde..jinou trubkou..tím pádem navenek vypadá, že průtok směrem vodárna→ domácnost je 3.

Pro zadání s určeným minimálním tokem

V této variantě je pro každou hranu $e\in E(G)$ zadáno nejen horní omezení $q(e)$, ale i minimální požadavek $r(e)\in R_{0}^{+}$ na tok. Tok $f\colon E(G)\to R_{0}^{+}$ je přípustný, pokud každá hrana splňuje $r(e)\leq f(e)\leq q(e)$. Úlohou pak může být nalezení maximálního, minimálního, nebo libovolného přípustného toku sítí.

Nejprve se budeme zabývat hledáním libovolného přípustného toku. Úlohu převedeme na hledání maximálního toku v síti $G'$ bez minimálních požadavků, která ze zadané sítě $G$ vznikne následujícími úpravami:

• přidáme hranu ze stoku do zdroje s nekonečnou kapacitou
• přidáme dva nové uzly, fiktivní zdroj $s'$ a fiktivní stok $t'$, které budou v síti $G'$ zdrojem a stokem
• za každou hranu $e=(u,v)$ sítě $G$ s kladným minimálním požadavkem $r(e)$ přidáme do $G'$ hrany $(u,t')$ a $(s',v)$, kterým nastavíme kapacity na $r(e)$; minimální požadavek na hraně $e$ zrušíme a nastavíme jí kapacitu $q'(e)=q(e)-r(e)$
• pokud nyní ze zdroje $s'$ vychází více hran do jednoho vrcholu, sloučíme tyto hrany do jedné o kapacitě rovné součtu kapacit původních hran; to samé uděláme, pokud do $t'$ vchází více hran ze stejného vrcholu

V síti $G'$ nalezneme maximální tok $f'$. Nejprve uvažujme případ, kdy každá hrana vycházející z $s'$ je nasycena, a tedy i každá hrana vcházející do $t'$ je nasycena. To znamená, že za každou hranu $e=(u,v)$ původní sítě $G$ s kladným $r(e)$ teče tok velikosti $r(e)$ z $u$ do $t'$ a z $s'$ do $v$. Tento tok přesměrujeme, aby tekl hranou $e$. Hranou $e$ tak teče tok velikosti $f'(e)+r(e)$, což nepřekračuje její kapacitu, protože $f'(e)\leq q'(e)=q(e)-r(e)$. Po následném odstranění uzlů a hran nově přidaných do $G'$ dostaneme přípustný tok sítí $G$. V případě, kdy některá hrana vycházející z $s'$ nasycena není, znamená to, že v $G$ neexistuje žádný přípustný tok. Pokud by totiž existoval, mohli bychom ho přeměnit na tok sítí $G'$, kde by každá hrana vycházející z $s'$ nasycena byla a tento tok by byl větší než $f'$.

Tento přípustný tok můžeme následně zlepšovat přidáváním, nebo ubíráním toku po zlepšujících cestách. V případě hledání maximálního toku je cesta $P=\langle s=u_{0},u_{1},\ldots ,u_{n}=t\rangle$, zlepšující, pokud pro každou dvojici $(u_{i},u_{i+1})$ platí, že $(u_{i},u_{i+1})$ je hranou $G$ a $f((u_{i},u_{i+1}))<q((u_{i},u_{i+1}))$, nebo $(u_{i+1},u_{i})$ je hranou $G$ a $f((u_{i+1},u_{i}))>r((u_{i+1},u_{i}))$. Po této cestě můžeme tok zvětšit. V případě hledání minimálního toku je $P=\langle s=u_{0},u_{1},\ldots ,u_{n}=t\rangle$, zlepšující, pokud pro každou dvojici $(u_{i},u_{i+1})$ platí, že $(u_{i},u_{i+1})$ je hranou $G$ a $f((u_{i},u_{i+1}))>r((u_{i},u_{i+1}))$, nebo $(u_{i+1},u_{i})$ je hranou $G$ a $f((u_{i+1},u_{i}))<q((u_{i+1},u_{i}))$. Po této cestě můžeme tok zmenšit.

Implementace

• Implementace v Javascript

Časová složitost

metoda NajdiCestu	O(|V|+|E|)
metoda ZvyšTok	O(|V'|)
celý algoritmus	O(|V|·|E|2), O(|V|2·|E|) nebo O(|V|3)

Pokud algoritmus nenaimplementujeme chytrým způsobem, je jeho časová složitost nezávislá na velikosti vstupu – závisí na kapacitách jednotlivých hran:

• Pro celočíselné kapacity hran to znamená, že algoritmus skončí v konečném čase s časovou složitostí O(součet kapacit všech hran) (horní mez je dána tím, že v každém kroku zvýšíme tok alespoň jednou hranou alespoň o 1 a maximální tok nikdy nemůže být vyšší než součet kapacit všech hran).
• Pro neceločíselné kapacity hran algoritmus může být nekonečný (neplatí zde předchozí předpoklad o zvyšování toku alespoň o 1 v každém kroku).

Související články

• Tok v síti
• Fordova-Fulkersonova věta
• Fordův-Fulkersonův značkovací algoritmus
• Dinicův algoritmus
• Goldbergův algoritmus

Externí odkazy

• Obrázky, zvuky či videa k tématu Fordův-Fulkersonův algoritmus na Wikimedia Commons

• Tomáš Dvořák: Toky v sítích
• Moderní algoritmy pro hledání maximálního toku v síti
• Jakub Černý: Základní grafové algoritmy (texty v pdf)
• Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů
• Interaktivní demonstrace
• Toky v sítích – úvod do toků v sítích, animace Ford-Fulkersonova algoritmu