Ponieważ również wyszukiwanie ścieżki powiększającej można zrealizować w czasie złożoność czasowa metody Forda-Fulkersona, to
W rzeczywistości, jedna z popularniejszych implementacji tej metody, algorytm Edmondsa-Karpa ma złożoność
Przykład Poniższy przykład przedstawia początkowe kroki metody Forda-Fulkersona w sieci z 4 wierzchołkami, źródłem A oraz ujściem D. Ścieżki powiększające są wyszukiwane za pomocą przeszukiwania w głąb, w którym sąsiadujące wierzchołki są odwiedzane w kolejności alfabetycznej. Jest to najgorszy możliwy przypadek, gdyż w każdej iteracji pętli głównej procedury przepływ jest powiększany tylko o 1.
Ścieżka Przepustowość Otrzymany przepływ Sytuacja początkowa Plik:ff-flow 0.png Plik:ff-flow 1.png Plik:ff-flow 2.png Sytuacja końcowa Plik:ff-flow f.png
Warto zwrócić uwagę, w jaki sposób przepływ „wraca” z wierzchołka C do B po wykorzystaniu ścieżki A,C,B,D.
Bibliografia Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, WNT 2004, .
Kategoria:Teoria grafów