Алгоритм Басакера Гоуэна

Контенус

Также известный как алгоритм Роя, алгоритм Басакера Гоуэна вычисляет максимальный расход при минимальных затратах.

Принцип прост, поиск возрастающего пути осуществляется вычислением кратчайший путь (самый дешевый путь). Критерии оптимальности эквивалентны задаче потока.

Алгоритм сводится к следующему:

Построить график pcc (кратчайший путь) из графика отклонения потока
- дуга, идентичная графику отклонений
- цена, соответствующая исходной дуге, если в том же направлении, противоположная, если нет
Ищите pcc от s до t
- если он существует, то это возрастающий путь, насыщаем его и возвращаемся к предыдущему шагу
- если пути нет, конец алгоритма.