Fordův–Fulkersonův značkovací algoritmus

Fordův-Fulkersonův značkovací algoritmus je obecný postup značkování nenasycené cesty v grafu při výpočtu maximálního toku.

Maximální tok v grafu při užití Fordovy-Fulkersonovy metody

Nechť X^k je současný maximální tok grafem. Nechť x^k je nalezený přírůstek maximálního toku v grafu.

Pak nový maximální tok lze vyjádřit jako X^k+1 = X^k + x^k.

Oprava současných toků

Opravíme toky v grafu na hranách na cestě označené Fordovou-Fulkersonovou metodou.

Nechť x_ij je současný tok hranou h_ij.

• pro nenasycené hrany orientované ve směru toku se nový tok rovná x^k+1_ij = x^k_ij + x^k

• pro hrany, kde existuje tok orientovaný proti směru současného " - x_ij " se nový tok rovná x^k+1_ij = - x^k_ij + x^k

• pro ostatní se tok nemění x^k+1 = x^k

Fordův-Fulkersonův značkovací algoritmus

1. Označme vstupní uzel sítě značkou " +0 "
2. Hledáme cestu z vstupního uzlu do výstupního uzlu sítě. Každý vedlejší uzel j, do něhož existuje nenasycená cesta z uzlu i ve směru toku označíme značkou " + i ", každý vedlejší uzel, který obsahuje tok proti směru proudu " - x_ij" označíme značkou " -i ". Určíme hodnotu přírůstku toku x^k jako x^k = min (k_ij - x_ij), kde k_ij je kapacita hrany h_ij.
3. Pokud nejsme schopni nalézt touto metodou cestu ze vstupu do výstupu, výpočet končí. Současný nalezený maximální tok je konečným maximálním tokem na síti.

Literatura

Fiala Petr - Řízení projektů, 2. vydání, Praha, 2008, ISBN 978-80-245-1413-0