300px Najkrótsza ścieżka: AB (3-1 = 2), BC (4-1 = 3), CE (2-0 = 2), ED (0-(-1) = 1), DF (6-3 = 3), FG (9-3 = 6). Minimalna pojemność residualna: 1.
Krawędź ED nie występuje w oryginalnym grafie (jej pojemność to 0), jest jednak obecna w sieci residualnej – przepływ na niej wynosi -1, gdyż przepływ na DE wynosi 1. Stąd pojemność residualna ED jest równa 1 i możemy tej krawędzi użyć w ścieżce powiększającej. 300px
W powstałej sieci nie ma już ścieżek powiększających, zatem znaleziony przepływ o wielkości 5 jest maksymalny. Przykład dobrze ilustruje podstawową własność algorytmu Edmondsa-Karpa: długości ścieżek powiększających w kolejnych krokach nie mogą maleć.
Zobacz też metoda Forda-Fulkersona problem maksymalnego przepływu
Przypisy
Linki zewnętrzne Algorytm Edmondsa-Karpa na wazniak.mimuw.edu.pl
Kategoria:Algorytmy grafowe