Edmondsův–Karpův algoritmus

Edmondsův-Karpův algoritmus je v informatice a teorii grafů implementací Fordovy-Fulkersonovy metody pro výpočet maximálního toku v síti s časovou složitostí ${\displaystyle O(VE^{2})}$. Je asymptoticky pomalejší než Goldbergův algoritmus s časovou složitostí ${\displaystyle O(V^{3})}$, ale v praxi je rychlejší pro řídké grafy. Dinic, ruský vědec, publikoval algoritmus poprvé v roce 1970^[1] nezávisle na publikování stejného algoritmu Kanaďanem Jackem Edmondsem a Američanem Richardem Karpem v roce 1972^[2] (údajně objeven dříve). Dinicův algoritmus obsahuje navíc techniky, které redukují časovou složitost na ${\displaystyle O(V^{2}E)}$.

Algoritmus je téměř identický s Fordovým-Fulkersonovým algoritmem, až na to, že je definováno pořadí výběru zlepšující cesty v případě existence většího počtu zlepšujících cest. Vybraná zlepšující cesta musí být vždy nejkratší možná. Pro důkaz korektnosti a časové složitosti ${\displaystyle O(VE^{2})}$ jsou podstatné následující vlastnosti:

• délka nalezené zlepšující cesty v průběhu algoritmu nikdy neklesá
• je-li v aktuálním kroku algoritmu měněn tok hranou jejíž tok byl měněn v některém z předchozích kroků, pak je délka zlepšující cesty v aktuálním kroku ostře větší než v příslušném kroku předchozím
• cesta ze zdroje do spotřebiče je nejvýše V dlouhá a lze ji nalézt v čase ${\displaystyle O(E)}$.

Důkaz je dostupný v.^[3]

Pro podrobnější popis vizte Fordův-Fulkersonův algoritmus.

algorithm EdmondsKarp
   input:
       C[1..n, 1..n] (Matice kapacit)
       E[1..n, 1..?] (Seznam sousedů)
       s             (Zdroj)
       t             (Spotřebič)
   output:
       f             (Hodnota maximálního toku)
       F             (Matice dávající korektní tok s maximální hodnotou)
   f := 0 (Na začátku je tok nula)
   F := array(1..n, 1..n) (Reziduální kapacita z u do v je C[u,v] - F[u,v])
   forever
       m, P := BreadthFirstSearch(C, E, s, t)
       if m = 0
           break
       f := f + m
       (Vyhledává backtrackingem a vypisuje tok)
       v := t
       while v ≠ s
           u := P[v]
           F[u,v] := F[u,v] + m
           F[v,u] := F[v,u] - m
           v := u
   return (f, F)

algorithm BreadthFirstSearch
   input:
       C, E, s, t
   output:
       M[t]          (Kapacita nalezené cesty)
       P             (Parent table)
   P := array(1..n)
   for u in 1..n
       P[u] := -1
   P[s] := -2 (ujistěte se, že zdroj není objeven podruhé) 
   M := array(1..n) (Kapacita nalezené cesty k vrcholu)
   M[s] := ∞
   Q := queue()
   Q.push(s)
   while Q.size() > 0
       u := Q.pop()
       for v in E[u]
           (Jestli je dostupná kapacita a v ještě nebylo nalezené)
           if C[u,v] - F[u,v] > 0 and P[v] = -1
               P[v] := u
               M[v] := min(M[u], C[u,v] - F[u,v])
               if v ≠ t
                   Q.push(v)
               else
                   return M[t], P
   return 0, P

Je daná síť o sedmi vrcholech, zdrojem A, spotřebičem G a kapacitami jako na obrázku:

Dvojice ${\displaystyle f/c}$ na hranách reprezentují současný tok ${\displaystyle f}$ a kapacitu ${\displaystyle c}$. Dostupná kapacita hrany z vrcholu ${\displaystyle u}$ do vrcholu ${\displaystyle v}$ je ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$, tedy celková kapacita minus použitý tok. Je-li tok hranou z vrcholu ${\displaystyle u}$ do vrcholu ${\displaystyle v}$ záporný, přičítá se ke kapacitě.

Kapacita	Cesta
	Výsledná síť
${\displaystyle \min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=}$ ${\displaystyle \min(3-0,2-0,1-0)=}$ ${\displaystyle \min(3,2,1)=1}$	${\displaystyle A,D,E,G}$
${\displaystyle \min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=}$ ${\displaystyle \min(3-1,6-0,9-0)=}$ ${\displaystyle \min(2,6,9)=2}$	${\displaystyle A,D,F,G}$
${\displaystyle \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))=}$ ${\displaystyle \min(3-0,4-0,1-0,6-2,9-2)=}$ ${\displaystyle \min(3,4,1,4,7)=1}$	${\displaystyle A,B,C,D,F,G}$
${\displaystyle \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))=}$ ${\displaystyle \min(3-1,4-1,2-0,0--1,6-3,9-3)=}$ ${\displaystyle \min(2,3,2,1,3,6)=1}$	${\displaystyle A,B,C,E,D,F,G}$

Všimněte si, jak se délka zlepšující cesty nalezené algoritmem nikdy nezmenšuje. Nalezené cesty jsou nejkratší možné. Nalezený tok se rovná kapacitě přes minimální řez v grafu oddělující zdroj a spotřebič. V tomto grafu je pouze jeden minimální řez, rozdělující vrcholy na množiny ${\displaystyle \{A,B,C,E\}}$ a ${\displaystyle \{D,F,G\}}$ s kapacitou ${\displaystyle c(A,D)+c(C,D)+c(E,G)=3+1+1=5}$.

• Algorithms and Complexity (strany 63 - 69)