Алгоритм Беллмана – Форда - Bellman–Ford algorithm

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

Учебный класс	Задача поиска кратчайшего пути с одним источником (для взвешенных ориентированных графов)
Структура данных	График
Наихудшая производительность	${\ Displaystyle \ Theta (| V || E |)}$
Лучшая производительность	${\ Displaystyle \ Theta (| E |)}$
Сложность пространства в наихудшем случае	${\ Displaystyle \ Theta (| V |)}$

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

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

Алгоритм

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

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

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

function BellmanFord(list vertices, list edges, vertex source) is

    // This implementation takes in a graph, represented as
    // lists of vertices (represented as integers [0..n-1]) and edges,
    // and fills two arrays (distance and predecessor) holding
    // the shortest path from the source to each vertex

    distance := list of size n
    predecessor := list of size n

    // Step 1: initialize graph
    for each vertex v in vertices do

        distance[v] := inf             // Initialize the distance to all vertices to infinity
        predecessor[v] := null         // And having a null predecessor
    
    distance[source] := 0              // The distance from the source to itself is, of course, zero

    // Step 2: relax edges repeatedly
    
    repeat |V|−1 times:
         for each edge (u, v) with weight w in edges do
             if distance[u] + w < distance[v] then
                 distance[v] := distance[u] + w
                 predecessor[v] := u

    // Step 3: check for negative-weight cycles
    for each edge (u, v) with weight w in edges do
        if distance[u] + w < distance[v] then
            error "Graph contains a negative-weight cycle"

    return distance, predecessor

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

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

Правильность алгоритма можно показать по индукции :

Лемма . После того, как я повторения для цикла,

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

Доказательство . Для базового случая индукции, рассмотрим i=0и момент , прежде чем для цикла выполняются в первый раз. Затем для исходной вершины 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

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

Обнаружение отрицательных циклов

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

Приложения в маршрутизации

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

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

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

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

Улучшения

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

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

Йен (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 к . ${\ displaystyle | V | / 2}$

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

Примечания

использованная литература

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

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

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

• Банг-Йенсен, Йорген; Гутин, Григорий (2000). «Раздел 2.3.4: Алгоритм Беллмана-Форда-Мура». Орграфы: теория, алгоритмы и приложения (Первое изд.). ISBN 978-1-84800-997-4.
• Шрайвер, Александр (2005). «К истории комбинаторной оптимизации (до 1960 г.)» (PDF) . Справочник по дискретной оптимизации . Эльзевьер: 1–68.
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. Введение в алгоритмы . MIT Press и McGraw-Hill., Второе издание. MIT Press и McGraw-Hill, 2001. ISBN  0-262-03293-7 . Раздел 24.1: Алгоритм Беллмана – Форда, стр. 588–592. Задача 24-1, стр. 614–615. Третье издание. MIT Press, 2009. ISBN  978-0-262-53305-8 . Раздел 24.1: Алгоритм Беллмана – Форда, стр. 651–655.
• Heineman, Джордж Т .; Поллис, Гэри; Селькоу, Стэнли (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 . Проверено 28 мая 2007 .