Edmonds-Karpův algoritmus

Z Wikipedie, otevřené encyklopedie

V informatice a teorii grafů je Edmonds-Karpův algoritmus implementací Ford-Fulkersonovy metody pro výpočet maximálního toku v síti s časovou složitostí O(VE2). Je asymptoticky pomalejší než Goldbergův algoritmus s časovou složitostí O(V3), 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 O(V2E).

Obsah

[editovat] Algoritmus

Algoritmus je téměř identický s Ford-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 O(VE2) 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 O(E).

Důkaz je dostupný v [3].

[editovat] Pseudokód

Projekt Wikibooks nabízí knihu v angličtině na téma:
Pro podrobnejší popis viď Ford-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] := &infin
   Q := queue()
   Q.push(s)
   while Q.size() > 0
       u := Q.pop()
       for v in E[u]
           (Jestli je dostupná kapacita a v ješte nebylo nelezené)
           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

[editovat] Příklad

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

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

Kapacita Cesta
Výsledná síť
min(cf(A,D),cf(D,E),cf(E,G)) =

min(3 − 0,2 − 0,1 − 0) =
min(3,2,1) = 1

A,D,E,G
min(cf(A,D),cf(D,F),cf(F,G)) =

min(3 − 1,6 − 0,9 − 0) =
min(2,6,9) = 2

A,D,F,G
min(cf(A,B),cf(B,C),cf(C,D),cf(D,F),cf(F,G)) =

min(3 − 0,4 − 0,1 − 0,6 − 2,9 − 2) =
min(3,4,1,4,7) = 1

A,B,C,D,F,G
min(cf(A,B),cf(B,C),cf(C,E),cf(E,D),cf(D,F),cf(F,G)) =

min(3 − 1,4 − 1,2 − 0,0 − − 1,6 − 3,9 − 3) =
min(2,3,2,1,3,6) = 1

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 {A,B,C,E} a {D,F,G} s kapacitou c(A,D) + c(C,D) + c(E,G) = 3 + 1 + 1 = 5.

[editovat] Reference

  1. E. A. Dinic. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Doklady, 1970, čís. Vol 11, s. 1277-1280.
  2. EDMONDS, Jack; KARP, Richard M.. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 1972, čís. 19, s. 248-264. 2. vydání. Dostupný z www: <[1]> [cit. 2007-03-26].
  3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest a Clifford Stein. Introduction to Algorithms. [s.l.]: MIT Press and McGraw-Hill, 2001. (Second edition.) ISBN 0-262-53196-8. Kapitola 26.2, s. 660-663.

[editovat] Externí odkazy

V jiných jazycích