Алгоритми та структури даних · Senior · Запитання 52 з 75
Який алгоритм знаходить максимальний потік у мережі?
- ✓Правильна відповідь: Едмондс-Карп (Форд-Фалкерсон з BFS)
- 2Перевірка циклу Флойда «черепаха й заєць»
- 3Мінімальне кістякове дерево Крускала
Пояснення
Він раз у раз знаходить найкоротший шлях доповнення через BFS і пускає ним потік, за O(V × E²). Максимальний потік розв'язує й двочасткове паросполучення, наприклад розподіл задач між виконавцями.