Algorytmy i struktury danych · Senior · Pytanie 52 z 75
Który algorytm znajduje maksymalny przepływ w sieci?
- ✓Poprawna odpowiedź: Edmonds-Karp (Ford-Fulkerson z BFS)
- 2Sprawdzanie cyklu Floyda „żółw i zając”
- 3Minimalne drzewo rozpinające Kruskala
Wyjaśnienie
Wielokrotnie znajduje najkrótszą ścieżkę powiększającą przez BFS i puszcza nią przepływ, w O(V × E²). Maksymalny przepływ rozwiązuje też skojarzenia w grafach dwudzielnych, np. przydział zadań do wykonawców.