Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






БЕЛЛМАНА-ФОРДА




(С ОТРИЦАТЕЛЬНЫМИ ВЕСАМИ)

Этот рисунок показывает резуль­таты применения алгоритма Беллмана-Форда, который предназ­начен для поиска кратчайших путей из вершины 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) графа следующим образом:



mylektsii.ru - Мои Лекции - 2015-2018 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал