Algorytm Dynica – algorytm o złożoności czasowej
O(V2E) rozwiązuje problem maksymalnego przepływu w sieci przepływowej, umożliwiając identyfikację przepływu blokującego w sieci warstwowej. Algorytm ten został opracowany w 1970 roku przez izraelskiego profesora Chaima Dynica. Jego struktura jest zbliżona do algorytmu Edmondsa-Karpa.
Kroki algorytmu:
- Krok 1 – podziel graf na L warstw (przegląd wszerz)
- Krok 2 – stwórz ścieżki powiększające (przegląd w głąb), unikając przemieszczania się w obrębie tej samej warstwy
- Krok 3 – oblicz maksymalny przepływ
