Часть 5. Алгоритмы на графах. Если в аугментальном цикле содержится более одного заполненного или порожнего ребра, то алгоритм подстановки

Завершающий выбор, с которым нам приходится сталкиваться при разработке сете­вого симплексного алгоритма, касается стратегии выявления подходящих ребер и выбо­ра одного из них для включения в дерево. Нужно ли заводить специальную структуру дан­ных для хранения подходящих ребер? Если нужно, то какой сложностью должна обладать такая структура данных? Ответ на эти вопросы в какой-то степени зависит от приложе­ния и динамических характеристик процесса решения задачи в конкретных случаях. Если суммарное количество подходящих ребер невелико, то целесообразно заводить специаль­ную структуру данных, если большая часть ребер входит в число подходящих в течение продолжительного времени, то в специальной структуре нет необходимости. Поддержа­ние отдельных структур позволяет снизить затраты ресурсов на поиск подходящих ребер, но в то же время может потребовать выполнения дорогостоящих операций по обновле­нию результатов вычислений. Каким критерием мы воспользуемся для выбора нужного подходящего ребра из некоторого множества таких ребер? И снова нам предоставляется богатый выбор. Мы проанализируем примеры в наших реализациях, затем рассмотрим существующие альтернативы. Например, программа 22.13 демонстрирует функцию, кото­рая находит подходящее ребро минимальной приведенной стоимости: ни одно другое реб­ро не позволит построить цикл, в случае включения которого наращивание потока в цикле не приведет к уменьшению суммарной стоимости.

Программа 22.13. Поиск подходящих ребер____________________________________