Глава 21. Кратчайшие пути. • 21.138.Добавьте функцию-элемент к решению упражнения 21.137, которая дала бы клиенту возможность уменьшить стоимость ребра

• 21.138. Добавьте функцию-элемент к решению упражнения 21.137, которая дала бы
клиенту возможность уменьшить стоимость ребра. Она должна возвращать флаг, ко­
торый указывает, создает ли это действие отрицательный цикл. Если нет, то должны
обновиться матрицы путей и расстояний, отразив любой новый кратчайший путь. Фун­
кция должна выполняться за время, пропорциональное V¹.

• 21.139. Расширьте решение упражнения 21.138 функциями-элементами, которые раз­
решают клиентам вставлять и удалять ребра.

• 21.140. Разработайте алгоритм, который преодолевает барьер VE для задачи поиска
кратчайших путей в общих сетях с единственным источником для частного случая, ког­
да известно, что абсолютные значения весов ограничены некоторой константой.

Перспективы

Таблица 21.4 подводит итог алгоритмам, которые обсуждались в настоящей главе, и приводит характеристики их производительности для худшего случая. Эти алгоритмы ши­роко применимы, поскольку, как упоминалось в разделе 21.6, задачи поиска кратчайших путей связаны с большим числом других задач, имеющих конкретное прикладное значе­ние, что непосредственно приводит к эффективным алгоритмам для решения всего класса задач, или, по крайней мере, указывает на существование таких алгоритмов.

Таблица 21.4 Стоимости алгоритмов поиска кратчайших путей ____________

В этой таблице сравниваются стоимости (времена выполнения в худшем случае) различных алгоритмов поиска кратчайших путей, которые рассматривались в настоящей главе. Границы худшего случая, обозначенные как умеренные, не могут оказаться полезными в прогнозировании производительности на реальных сетях, в частности, сказанное относится к алгоритму Беллмана-Форда, который обычно выполняется за линейное время.