Algorytm Dynicaalgorytm o złożoności czasowej 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
Algorytm Dynica
Rodzaj

problem maksymalnego przepływu

Struktura danych

sieć przepływowa

Złożoność
Czasowa

O(V2E)