Algorytm Dynica

Algorytm Dynica

Rodzaj	problem maksymalnego przepływu
Struktura danych	sieć przepływowa
Złożoność
Czasowa	O(V2E)

Algorytm Dynica – algorytm o złożoności czasowej $O(V^{2}E)$ rozwiązujący problem maksymalnego przepływu w sieci przepływowej umożliwiający odnajdywanie przepływu blokującego w sieci warstwowej. Algorytm skonstruowany został w 1970 roku przez izraelskiego profesora - Chaima Dynica. Strukturą zbliżony jest do alg. Edmondsa-Karpa.

1. krok - dziel graf na L warstw (przegląd wszerz)
2. krok - utwórz ścieżki powiększające (przegląd w głąb), nie przemieszczając się względem tej samej warstwy
3. krok - wyznacz maksymalny przepływ