Алгоритм Беллмана–Форда

Алгоритм поиска кратчайших путей в графах

Алгоритм Беллмана –Форда — это алгоритм , который вычисляет кратчайшие пути от одной исходной вершины до всех других вершин во взвешенном орграфе . ^[1] Он медленнее алгоритма Дейкстры для той же задачи, но более универсален, так как способен обрабатывать графы, в которых некоторые веса ребер являются отрицательными числами. ^[2] Алгоритм был впервые предложен Альфонсо Шимбелем (1955), но вместо этого назван в честь Ричарда Беллмана и Лестера Форда-младшего , которые опубликовали его в 1958 и 1956 годах соответственно. ^[3] Эдвард Ф. Мур также опубликовал вариацию алгоритма в 1959 году, и по этой причине его также иногда называют алгоритмом Беллмана–Форда–Мура . ^[1]

Отрицательные веса ребер встречаются в различных приложениях графов. Вот почему этот алгоритм полезен. ^[4] Если граф содержит «отрицательный цикл» (т. е. цикл , сумма ребер которого дает отрицательное значение), который достижим из источника, то нет самого дешевого пути: любой путь, имеющий точку на отрицательном цикле, можно сделать дешевле, если обойти отрицательный цикл еще на один раз . В таком случае алгоритм Беллмана–Форда может обнаружить и сообщить об отрицательном цикле. ^{[1] [5]}

Алгоритм

В этом примере графа, предполагая, что A является источником, а ребра обрабатываются в наихудшем порядке, справа налево, требуется полная | V |−1 или 4 итерации для сходимости оценок расстояния. Наоборот, если ребра обрабатываются в наилучшем порядке, слева направо, алгоритм сходится за одну итерацию.

Как и алгоритм Дейкстры , алгоритм Беллмана–Форда действует путем релаксации , в котором приближения к правильному расстоянию заменяются лучшими, пока они в конечном итоге не достигнут решения. В обоих алгоритмах приблизительное расстояние до каждой вершины всегда является завышенной оценкой истинного расстояния и заменяется минимумом его старого значения и длины вновь найденного пути.

Однако алгоритм Дейкстры использует приоритетную очередь для жадного выбора ближайшей вершины, которая еще не была обработана, и выполняет этот процесс релаксации на всех ее исходящих ребрах; напротив, алгоритм Беллмана–Форда просто расслабляет все ребра и делает это раз, где — количество вершин в графе. ${\displaystyle |V|-1}$ ${\displaystyle |V|}$

В каждом из этих повторений число вершин с правильно рассчитанными расстояниями растет, из чего следует, что в конечном итоге все вершины будут иметь свои правильные расстояния. Этот метод позволяет применять алгоритм Беллмана–Форда к более широкому классу входных данных, чем алгоритм Дейкстры. Промежуточные ответы зависят от порядка ослабленных ребер, но окончательный ответ остается тем же.

Беллман–Форд работает за время , где и — количество вершин и ребер соответственно. ${\displaystyle O(|V|\cdot |E|)}$ ${\displaystyle |V|}$ ${\displaystyle |E|}$

Функция BellmanFord( список вершин, список ребер, источник вершины ) — это // Эта реализация берет граф, представленный в виде  // списков вершин (представленных как целые числа [0..n-1]) и ребер,  // и заполняет два массива (расстояние и предшественник), содержащих  // кратчайший путь от источника до каждой вершины расстояние := список размера n предшественник := список размера n // Шаг 1: инициализация графа  для каждой вершины v в вершинах do // Инициализируем расстояние до всех вершин до бесконечности расстояние[v] := инф // И имеющий нулевого предшественника предшественник[v] := null  // Расстояние от источника до него самого, конечно, равно нулю расстояние[источник] := 0 // Шаг 2: ослабить ребра многократно  повторить |V|−1 раз : для каждого ребра (u, v) с весом w в ребрах сделать  , если расстояние[u] + w < расстояние[v] , то расстояние[v] := расстояние[u] + w предшественник[v] := u // Шаг 3: проверка циклов с отрицательным весом  для каждого ребра (u, v) с весом w в ребрах do  if distance[u] + w < distance[v] then предшественник[v] := u // Существует отрицательный цикл; найти вершину в цикле visited := list размера n инициализирован значением false visited[v] := true  while  not visited[u] do visited[u] := true u := предшественник[u] // u — вершина в отрицательном цикле, находим сам цикл nцикл := [u] v := предшественник[u] пока v != u делает ncycle := конкатенация([v], ncycle) v := предшественник[v] ошибка "Граф содержит цикл с отрицательным весом", ncycle return distance, previous

Проще говоря, алгоритм инициализирует расстояние до источника равным 0, а все остальные узлы — бесконечностью. Затем для всех ребер, если расстояние до пункта назначения можно сократить, взяв ребро, расстояние обновляется до нового меньшего значения.

Ядром алгоритма является цикл, который сканирует все ребра в каждом цикле. Для каждого , в конце -й итерации, из любой вершины v , следуя по следу предшественника, записанному в предшественнике, получается путь, общий вес которого не превышает distance[v] , и, кроме того, distance[v] является нижней границей длины любого пути от источника до v , который использует не более i ребер. ${\displaystyle i\leq |V|-1}$ ${\displaystyle i}$

Поскольку самый длинный возможный путь без цикла может быть ребрами, ребра должны быть просканированы раз, чтобы гарантировать, что кратчайший путь был найден для всех узлов. Выполняется окончательное сканирование всех ребер, и если какое-либо расстояние обновляется, то был найден путь длины ребер, что может произойти только в том случае, если в графе существует хотя бы один отрицательный цикл. ${\displaystyle |V|-1}$ ${\displaystyle |V|-1}$ ${\displaystyle |V|}$

Ребро (u, v), найденное на шаге 3, должно быть достижимо из отрицательного цикла, но оно не обязательно является частью самого цикла, поэтому необходимо следовать по пути предшественников в обратном направлении, пока не будет обнаружен цикл. Приведенный выше псевдокод использует булев массив ( visited) для поиска вершины в цикле, но любой алгоритм поиска цикла может быть использован для поиска вершины в цикле.

Распространенным улучшением при реализации алгоритма является ранний возврат, когда итерация шага 2 не может ослабить ни одно ребро, что подразумевает, что все кратчайшие пути были найдены, и, следовательно, нет отрицательных циклов. В этом случае сложность алгоритма уменьшается с до , где — максимальная длина кратчайшего пути в графе. ${\displaystyle O(|V|\cdot |E|)}$ ${\displaystyle O(l\cdot |E|)}$ ${\displaystyle l}$

Доказательство правильности

Корректность алгоритма можно показать по индукции : ^[2]

Лемма . После i повторений цикла for ,

• если Distance( u ) не равно бесконечности, то оно равно длине некоторого пути от s до u ; и
• если существует путь из s в u с не более чем i ребрами, то Distance(u) не превышает длины кратчайшего пути из s в u с не более чем i ребрами.

Доказательство . Для базового случая индукции рассмотрим i=0и момент до того, как цикл for будет выполнен в первый раз. Затем для исходной вершины , source.distance = 0что верно. Для других вершин u , , что также верно, поскольку нет пути от источника до u с 0 ребрами.u.distance = infinity

Для индуктивного случая сначала докажем первую часть. Рассмотрим момент, когда расстояние вершины обновляется на v.distance := u.distance + uv.weight. По индуктивному предположению, u.distance— длина некоторого пути от источника до u . Тогда u.distance + uv.weight— длина пути от источника до v , который следует по пути от источника до u и затем идет в v .

Для второй части рассмотрим кратчайший путь P (их может быть больше одного) от источника до v с не более чем i ребрами. Пусть u — последняя вершина перед v на этом пути. Тогда часть пути от источника до u является кратчайшим путем от источника до u с не более чем i-1 ребрами, поскольку если бы это было не так, то должен быть некоторый строго более короткий путь от источника до u с не более чем i-1 ребрами, и мы могли бы затем добавить ребро uv к этому пути, чтобы получить путь с не более чем i ребрами, который строго короче, чем P — противоречие. По индуктивному предположению, u.distanceпосле i −1 итераций не более длины этого пути от источника до u . Следовательно, uv.weight + u.distanceне более длины P . На i ^-й итерации v.distanceсравнивается с uv.weight + u.distanceи устанавливается равным ему, если uv.weight + u.distanceменьше. Следовательно, после i итераций v.distanceне более длины P , т. е. длины кратчайшего пути от источника до v , который использует не более i ребер.

Если нет циклов с отрицательным весом, то каждый кратчайший путь посещает каждую вершину не более одного раза, поэтому на шаге 3 никаких дальнейших улучшений сделать нельзя. Наоборот, предположим, что никаких улучшений сделать нельзя. Тогда для любого цикла с вершинами v [0], ..., v [ k −1],

v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight

Суммируя по циклу, члены v [ i ].distance и v [ i −1 (mod k )].distance сокращаются, оставляя

0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

Т.е. каждый цикл имеет неотрицательный вес.

Нахождение отрицательных циклов

Когда алгоритм используется для поиска кратчайших путей, существование отрицательных циклов является проблемой, не позволяющей алгоритму найти правильный ответ. Однако, поскольку он завершается при обнаружении отрицательного цикла, алгоритм Беллмана–Форда может использоваться для приложений, в которых это является целью поиска – например, в методах отмены циклов в анализе сетевого потока . ^[1]

Применение в маршрутизации

Распределенный вариант алгоритма Беллмана-Форда используется в протоколах маршрутизации на основе векторов расстояний , например, в протоколе маршрутной информации (RIP). Алгоритм является распределенным, поскольку он включает в себя ряд узлов (маршрутизаторов) в пределах автономной системы (AS) , набора IP-сетей, обычно принадлежащих интернет-провайдеру. Он состоит из следующих шагов:

1. Каждый узел вычисляет расстояния между собой и всеми другими узлами в пределах AS и сохраняет эту информацию в виде таблицы.
2. Каждый узел отправляет свою таблицу всем соседним узлам.
3. Когда узел получает таблицы расстояний от своих соседей, он вычисляет кратчайшие маршруты ко всем остальным узлам и обновляет свою собственную таблицу, чтобы отразить любые изменения.

Основными недостатками алгоритма Беллмана–Форда в данной ситуации являются:

• Он плохо масштабируется.
• Изменения в топологии сети не отражаются быстро, поскольку обновления распространяются от узла к узлу.
• Считайте до бесконечности, если сбои в работе соединения или узла делают узел недоступным для некоторого набора других узлов, эти узлы могут бесконечно долго постепенно увеличивать свои оценки расстояния до него, и в то же время могут возникать петли маршрутизации.

Улучшения

Алгоритм Беллмана–Форда может быть улучшен на практике (хотя и не в худшем случае) за счет наблюдения, что если итерация основного цикла алгоритма завершается без внесения каких-либо изменений, алгоритм может быть немедленно завершен, поскольку последующие итерации не будут вносить никаких изменений. При таком условии раннего завершения основной цикл может в некоторых случаях использовать гораздо меньше, чем | V | − 1 итераций, даже если наихудший случай алгоритма остается неизменным. Все следующие улучшения сохраняют временную сложность наихудшего случая. ${\displaystyle O(|V|\cdot |E|)}$

Разновидность алгоритма Беллмана–Форда, описанная Муром (1959), уменьшает количество шагов релаксации, которые необходимо выполнить в каждой итерации алгоритма. Если вершина v имеет значение расстояния, которое не изменилось с момента последнего расслабления ребер из v , то нет необходимости расслаблять ребра из v во второй раз. Таким образом, по мере того, как число вершин с правильными значениями расстояния растет, число, чьи исходящие ребра, которые необходимо ослабить в каждой итерации, сокращается, что приводит к постоянной экономии времени для плотных графов . Эта вариация может быть реализована путем сохранения набора вершин, чьи исходящие ребра необходимо ослабить, удаления вершины из этого набора, когда ее ребра ослаблены, и добавления в набор любой вершины, чье значение расстояния изменилось на шаг релаксации. В Китае этот алгоритм был популяризирован Фаньдином Дуаном, который заново открыл его в 1994 году как «алгоритм кратчайшего пути с большей скоростью». ^[6]

Йен (1970) описал еще одно улучшение алгоритма Беллмана–Форда. Его улучшение сначала назначает некоторый произвольный линейный порядок всем вершинам, а затем разбивает множество всех ребер на два подмножества. Первое подмножество, E _f , содержит все ребра ( v _i , v _j ) такие, что i < j ; второе, E _b , содержит ребра ( v _i , v _j ) такие, что i > j . Каждая вершина посещается в порядке v ₁ , v ₂ , ..., v _{| V |} , ослабляя каждое исходящее ребро из этой вершины в E _f . Затем каждая вершина посещается в порядке v _{| V |} , v _{| V |−1} , ..., v ₁ , ослабляя каждое исходящее ребро из этой вершины в E _b . Каждая итерация основного цикла алгоритма после первой добавляет по крайней мере два ребра к множеству ребер, ослабленные расстояния которых соответствуют правильным расстояниям кратчайшего пути: одно из E _f и одно из E _b . Эта модификация уменьшает наихудшее число итераций основного цикла алгоритма с | V | − 1 до . ^{[7] [8]} ${\displaystyle |V|/2}$

Другое улучшение, Баннистера и Эппштейна (2012), заменяет произвольный линейный порядок вершин, используемый во втором улучшении Йена, случайной перестановкой . Это изменение делает наихудший случай для улучшения Йена (в котором ребра кратчайшего пути строго чередуются между двумя подмножествами E _f и E _b ) крайне маловероятным. При случайно переставленном порядке вершин ожидаемое число итераций, необходимых в основном цикле, составляет не более . ^[8] ${\displaystyle |V|/3}$

Примечания

1. Банг-Дженсен и Гутин (2000)
2. Лекция 14 stanford.edu
3. Схрейвер (2005)
4. Седжвик (2002).
5. Клейнберг и Тардос (2006).
6. Дуань, Фандин (1994). «关于最短路径的SPFA快速算法 [Об алгоритме SPFA]». Журнал Юго-Западного университета Цзяотун . 29 (2): 207–212.
7. Кормен и др., 4-е изд., Проблема 22-1, стр. 640.
8. См. веб-упражнения Седжвика для Алгоритмов , 4-е изд., упражнения 5 и 12 (получено 30.01.2013).

Ссылки

Первоисточники

• Шимбел, А. (1955). Структура в сетях связи . Труды симпозиума по информационным сетям. Нью-Йорк, Нью-Йорк: Политехническое издательство Политехнического института Бруклина. С. 199–203.
• Беллман, Ричард (1958). «О проблеме маршрутизации». Quarterly of Applied Mathematics . 16 : 87–90. doi : 10.1090/qam/102435 . MR  0102435.
• Форд, Лестер Р. младший (14 августа 1956 г.). Теория сетевых потоков. Статья P-923. Санта-Моника, Калифорния: RAND Corporation.
• Мур, Эдвард Ф. (1959). Кратчайший путь через лабиринт . Proc. Internat. Sympos. Switching Theory 1957, Часть II. Кембридж, Массачусетс: Harvard Univ. Press. С. 285–292. MR  0114710.
• Йен, Джин Й. (1970). «Алгоритм поиска кратчайших маршрутов от всех исходных узлов до заданного пункта назначения в общих сетях». Quarterly of Applied Mathematics . 27 (4): 526–530. doi : 10.1090/qam/253822 . MR  0253822.
• Баннистер, М.Дж.; Эппштейн, Д. (2012). Рандомизированное ускорение алгоритма Беллмана–Форда . Аналитическая алгоритмика и комбинаторика (ANALCO12), Киото, Япония. стр. 41–47. arXiv : 1111.5414 . doi :10.1137/1.9781611973020.6.

Вторичные источники

• Форд, Л. Р. Мл .; Фулкерсон, Д. Р. (1962). «Алгоритм кратчайшей цепи». Потоки в сетях . Princeton University Press. С. 130–134.
• Банг-Йенсен, Йорген; Гутин, Грегори (2000). "Раздел 2.3.4: Алгоритм Беллмана-Форда-Мура". Диграфы: теория, алгоритмы и приложения (первое издание). Springer. ISBN 978-1-84800-997-4.
• Шрайвер, Александр (2005). «К истории комбинаторной оптимизации (до 1960 г.)» (PDF) . Справочник по дискретной оптимизации . Elsevier: 1–68.
• Кормен, Томас Х.; Лейзерсон , Чарльз Э .; Ривест, Рональд Л. Введение в алгоритмы . MIT Press и McGraw-Hill., Четвертое издание. MIT Press, 2022. ISBN 978-0-262-04630-5 . Раздел 22.1: Алгоритм Беллмана–Форда, стр. 612–616. Задача 22–1, стр. 640. 
• Heineman, George T.; Pollice, Gary; Selkow, Stanley (2008). "Глава 6: Графовые алгоритмы". Алгоритмы в двух словах . O'Reilly Media . стр. 160–164. ISBN 978-0-596-51624-6.
• Клейнберг, Джон ; Тардос, Эва (2006). Разработка алгоритмов . Нью-Йорк: Pearson Education, Inc.
• Седжвик, Роберт (2002). "Раздел 21.7: Отрицательные веса рёбер". Алгоритмы на Java (3-е изд.). ISBN 0-201-36121-3. Архивировано из оригинала 2008-05-31 . Получено 2007-05-28 .