Katedra telekomunikácií, FEI STU Bratislava

Analýza smerovacích algoritmov v počítačových a telekomunikačných sietiach

Ford-Fulkerson algoritmus

Obsah

Úvod

Algoritmus Ford-Fulkerson (FF) [1] rieši problém nájdenia maximálneho toku medzi dvoma uzlami siete. Ako jediný nezaručuje jeho nájdenie (čo neplatí pre celočíselné kapacity) a nie je polynomiálny.

Základné pojmy [2]

Hodnota hrán je daná funkciou kapacity c(i,j)≥0.

Tok v sieti je celočíselná funkcia f definovaná na hranách E, ktorá splňuje podmienku 0  f(i,j) c(i,j).

Podmienka zachovania – pre každý uzol j z V, ktorý nie je ani zdroj ani cieľ, suma tokov do j je rovná sume tokov z j.

Tok,ktorý spĺňa podmienku zachovania je nazývaný vhodný tok.

Nech f je vhodný tok v sieti G. Tok sieťou, označený f(G) je suma tokov vychádzajúcich zo zdroja s.

Nech f je vhodný tok v sieti G. Hrana (i,j) je:

  1. saturovaná ak f(i,j) = c(i,j)
  2. voľná ak f(i,j) = 0
  3. pozitívna ak 0 < f(i,j) < c(i,j)

Zlepšujúca cesta je alternatívna sekvencia hrán a vrcholov z s do t , v ktorej sa neopakuje žiadny vrchol a žiadna dopredná hrana nie je saturovaná a žiadna spätná nie je voľná.

Zbytková kapacita toku zlepšujúcej cesty je rovné minimu zvyškových kapacít všetkých hrán v ceste.

Problém maximálneho toku

Algoritmus pre daný graf G=(V,E), kapacitu c:E->R+, a dva uzly s a t, nájde maximálny tok medzi s-t.

Ford-Fulkersonov algoritmus

Následne si opíšeme Ford-Fulkersonov algoritmus na zistenie maximálneho toku medzi zdrojovým uzlom s a cieľovým uzlom t [1].

  1. (Inicializácia) Nech x je počiatočný vhodný tok x(e)=0 pre všetky hrany v E.
  2. Nájdeme zlepšovaciu cestu pomocou značkovacej procedúry(viz. nižšie) . Ak takáto cesta neexistuje medzi uzlami s a t, tak skonči. Aktuálny tok x je maximálny tok siete.
  3. Ak existuje zlepšujúca cesta vypočítame jej zbytkovú kapacitu d.
  4. Tok x položíme rovný
    • x(e)=x(e)+d ak e je dopredná hrana.
    • x(e)=x(e)-d ak e je spätná hrana.
    Vrátime sa do bodu 2.

Značkovacia procedúra

Značkovacia procedúra je súčasťou FF, ale z dôvodu jednoduchšieho pochopenia algoritmu ju uvádzame oddelene [1].

  1. Označkujeme zdrojový uzol s.
  2. Test, či je označkovaný cieľový uzol t. Ak áno, skončíme.
  3. Snaha o dopredné značkovanie. Ak existuje hrana h, že jej počiatočný vrchol má značku a koncový nemá značku pričom prípustný tok f(h) < c(h), potom koncový uzol označkujeme a hrana h sa stane súčasťou cesty. Pokračujeme v bode 2. Ak taká hrana neexistuje pokračujeme v bode 4.
  4. Snaha o spätné značkovanie. Ak existuje hrana h, že jej koncový vrchol má značku a počiatočný nemá značku pričom obmedzenie toku l(h) < f(h), potom počiatočný uzol označkujeme a hrana h sa stane súčasťou cesty. Pokračujeme v bode 2. Ak taká hrana neexistuje značkovacia procedúra skončí.

Zoznam literatúry

[1] http://jaja.kn.vutbr.cz/%7Epalubjak/ford.html
[2] Ford-Fulkerson Algorithm, http://www.cs.pitt.edu/~kirk/cs1501/notes/Ford-Fulkerson.doc
[3] http://www-b2.is.tokushima-u.ac.jp/%7Eikeda/suuri/maxflow/Maxflow.shtml