Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
БЕЛЛМАНА-ФОРДА
|
|
(С ОТРИЦАТЕЛЬНЫМИ ВЕСАМИ)
Этот рисунок показывает результаты применения алгоритма Беллмана-Форда, который предназначен для поиска кратчайших путей из вершины 4 в сети, изображенной на рис. 21.26. Алгоритм действует в режиме просмотра, где проверяются все ребра, исходящие из всех вершин, помещенных в очередь FIFO. Содержимое очереди показано ниже каждого рисунка графа с использованием затененных элементов, представляющих содержимое очереди для предыдущего прохода. Когда мы находим ребро, которое может уменьшить длину пути из вершины 4 в адресат, мы выполняем операцию ослабления, которая помещает вершину-адресат в очередь, а ребро — в SPT. Серые ребра на рисунках графа составляют SPT после каждого этапа, которое показано также в ориентированной форме в центре (все стрелки ребер направлены вниз). Мы начинаем с пустого SPT и вершины 4 в очереди (верхняя часть рисунка). На втором проходе мы выполняем ослабление вдоль ребер 4-2 и 4-3, оставляя в очереди вершины 2 и 3. На третьем проходе мы проверяем, но не выполняем ослабления вдоль 2-3 и затем также не выполняем ослабления вдоль 3-0 и 3-5, оставляя в очереди вершины 0 и 5. На четвертом проходе мы выполняем ослабление вдоль 5-1 и затем проверяем, но не выполняем ослабления вдоль 1-0 и 1-5, оставляя в очереди вершину 1. На последнем проходе (внизу) мы выполняем ослабление вдоль 1-2. Алгоритм изначально действует подобно BFS, однако в отличие от всех других методов поиска на графе, он может изменять ребра дерева, как это имело место на последнем шаге.
Часть 5. Алгоритмы на графах
Разумеется, исследовались и другие вариации алгоритма Беллмана-Форда, причем некоторые из них оказываются более быстрыми для задачи с одним источником, чем версия с очередью FIFO в программе 21.9, однако все они в худшем случае требуют времени, пропорционального, по крайней мере, VE (см., например, упражнение 21.132). Базовый алгоритм Беллмана-Форда был разработан десятки лет тому назад, и несмотря на впечатляюще большие шаги в плане достижения эффективности, которые мы наблюдали для множества других задач на графах, до сих пор не просматриваются алгоритмы с лучшей эффективностью для худшего случая на сетях с отрицательными весами.
По сравнению с алгоритмом Флойда, алгоритм Беллмана-Форда является также более эффективным методом для обнаружения, содержит ли сеть отрицательные циклы.
Свойство 21.22. С помощью алгоритма Беллмана-Форда можно решить задачу обнаружения отрицательного цикла за время, пропорциональное VE.
Доказательство: Основные положения доказательства свойства 21.21 справедливы даже при наличии отрицательных циклов. Если мы выполняем V-тую итерацию алгоритма, за которой следует любой шаг ослабления, то мы уже обнаружили кратчайший путь с V ребрами, который соединяет s с некоторой вершиной в сети. Любой такой путь должен содержать цикл (соединяющий некоторую вершину w с собой), и в соответствии с предположением индукции, этот цикл должен быть отрицательным, поскольку для того, чтобы w была включена в путь второй раз, путь из s во второе вхождение w должен быть более коротким, чем путь из s в первое вхождение w. Этот цикл будет также присутствовать в дереве, поэтому обнаружить циклы можно было бы и с помощью периодической проверки ребер из spt (см. упражнение 21. 134).
Сказанное остается в силе только для тех вершин, которые находятся в том же сильно связном компоненте, что и источник s. Чтобы обнаружить отрицательные циклы вообще, можно также вычислить сильно связные компоненты и инициализировать веса для одной вершины в каждом компоненте значениями 0 (см. упражнение 21.126) или добавить фиктивную вершину с ребрами в каждую из остальных вершин (см. упражнение 21.127). ■
В заключение этого раздела рассмотрим задачу поиска кратчайших путей для всех пар. Можно ли улучшить алгоритм Флойда, который выполняется за время, пропорциональное К3? Использование алгоритма Беллмана-Форда для решения задачи всех пар с помощью решения для каждой вершины задачи с одним источником приводит к худшему случаю времени выполнения, при котором время оказывается пропорциональным V2E. Мы не рассматриваем это решение более подробно, поскольку существует способ, гарантирующий возможность решения задачи для всех путей за время, пропорциональное VE log V. Он основан на идее, рассмотренной в начале этого раздела: превращение заданной сети в сеть, которая содержит только неотрицательные веса и имеет ту же структуру кратчайших путей.
Фактически, у нас имеется большая свобода в превращении одной сети в другую с отличными весами ребер, но с теми же кратчайшими путями. Предположим, что индексированный вершинами вектор wt содержит произвольное распределение весов на вершинах сети G. Для этих весов определим операцию повторного взвешивания, или переназначение весов, (reweighting) графа следующим образом: