Algorytm Dynica
Rodzaj | |
---|---|
Struktura danych | |
Złożoność | |
Czasowa | O(V2E) |
Algorytm Dynica – algorytm 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.
- krok - dziel graf na L warstw (przegląd wszerz)
- krok - utwórz ścieżki powiększające (przegląd w głąb), nie przemieszczając się względem tej samej warstwy
- krok - wyznacz maksymalny przepływ
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów | |
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |