Выбор расширенного пути в алгоритме ford fulkerson
Если в остаточной сети имеется много расширенных путей для данной сети потоков, какой путь я должен выбрать в первую очередь, чтобы найти пропускную способность?
1 ответ
Метод Форда-Фулкерсона не определяет, какой альтернативный путь использовать, если их несколько.
Но вы можете изменить алгоритм так, чтобы
Цель: выбрать дополнительные пути так, чтобы:
- Может найти эффективные пути расширения.
- Несколько итераций.
Эдмондс-Карп (1972) проанализировал две естественные эвристики для выбора пути увеличения. Выберите путь дополнения,
- Самое большое значение узкого места. (толстый путь) - Жадный алгоритм Меньше всего
- Количество дуг. (кратчайший путь, можно найти с помощью BFS)