Algoritmus Malhotra-Kumara-Maheshwari

Algoritmus Malhotra-Kumar-Maheshwari vám umožňuje najít maximální průtok v grafu.

Popis

Uvažujeme transportní síť sestávající z orientovaného grafu , kde je množina vrcholů, množina hran a tok . Pro každý vrchol je zaveden potenciál toku rovný maximálnímu dodatečnému toku, který může procházet tímto vrcholem. Následuje cyklus. Při každé iteraci je určen vrchol s minimálním potenciálem . Poté je zahájen tok velikosti od zdroje k jímce, který prochází tímto vrcholem. V tomto případě, pokud je zbytková kapacita hrany rovna nule, je tato hrana odstraněna. Všechny vrcholy, které nemají žádné vstupní a/nebo žádné odchozí hrany, jsou také odstraněny. Když je odstraněn vrchol, jsou odstraněny všechny sousední hrany. Bude tedy nalezen blokující (pseudo-maximální) tok. Chcete-li v grafu najít maximální průtok, musíte vyhledat blokující průtok a poté graf odpovídajícím způsobem upravit a tak dále, dokud se blokující průtok nebude rovnat nule. $G=(V,\;E)$ $PROTI$ $E$ $F$ $v\in V$ $r$ $\rho$ $\rho$

Obtížnost

Pokud jsou informace o příchozích a odchozích obloucích uloženy ve formě propojených seznamů , pak za účelem přeskočení toku budou při každé iteraci provedeny akce, kde odpovídá počtu hran, u kterých se zbytková propustnost snížila, ale zůstala kladná. a na počet odstraněných hran. Budou tedy provedeny akce k nalezení blokujícího vlákna . Hledání blokujícího vlákna bude provedeno jednou, protože počet hran na cestě od zdroje k propadu v blokujícím vláknu se nesníží. Pak se celá věc ukáže jako činy. $O(\left|V\right|+\left|E_{i}\right|)$ $\left|V\right|$ $\left|E_{i}\right|$ $\sum _{i}{O(\left|V\right|+\left|E_{i}\right|)}=O(\left|V\right|^{2})$ $O(\left|V\right|)$ $O(\left|V\right|^{3})$

Literatura

Malhotra VM, Kumar M. Pramodh, Maheshwari SN Algoritmus O(IVI 3 ) pro nalezení maximálních toků v sítích . — 1978.

Algoritmus Malhotra-Kumara-Maheshwari

Popis

Obtížnost

Literatura

Poznámky