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

Алгоритм Беллмана – Форда
Учебный класс	Проблема кратчайшего пути из одного источника (для взвешенных ориентированных графов)
Структура данных	График
Худший случай спектакль
Лучший случай спектакль
Худший случай космическая сложность

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

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

Алгоритм

В этом примере графа, предполагая, что A является источником и ребра обрабатываются в наихудшем порядке, справа налево, он требует полного

| V |-1

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

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

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

функция BellmanFord (список вершины, список края, вершина источник) является    // Эта реализация принимает граф, представленный как    // списки вершин (представленных целыми числами [0..n-1]) и ребер,    // и заполняет два массива (расстояние и предшественник), удерживая    // кратчайший путь от источника до каждой вершины    расстояние: = список размера п    предшественник: = список размера п    // Шаг 1: инициализировать график    для каждого вершина v в вершины делать        расстояние [v]: = инф             // Инициализируем расстояние до всех вершин до бесконечности до предшественника [v]: = ноль         // И имеющий нулевого предшественника     distance [source]: = 0 // Расстояние от источника до самого себя, конечно же, ноль // Шаг 2: несколько раз ослабляем края    повторение | V | −1 раз:        для каждого край (u, v) с вес w в края делать            если расстояние [u] + w <расстояние [v] тогда                расстояние [v]: = расстояние [u] + w предшественник [v]: = u // Шаг 3: проверка циклов с отрицательным весом    для каждого край (u, v) с вес w в края делать        если расстояние [u] + w <расстояние [v] тогда            ошибка «График содержит цикл с отрицательным весом» возвращаться расстояние, предшественник

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

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

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

Лемма. После я повторения за петля,

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

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

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

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

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

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

Подводя итоги цикла, v[я] .distance и v[я−1 (mod k)]. расстояние условия отменить, оставив

0 <= сумма от 1 до k из v [i-1 (mod k)] v [i]. Weight

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

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

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

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

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

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

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

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

Улучшения

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

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

Йена (1970) описал еще одно усовершенствование алгоритма Беллмана – Форда. Его усовершенствование сначала назначает произвольный линейный порядок всем вершинам, а затем разбивает множество всех ребер на два подмножества. Первое подмножество, E_ж, содержит все ребра (v_я, v_j) такие, что я < j; второй, E_б, содержит ребра (v_я, v_j) такие, что я > j. Каждая вершина посещается в порядке $v 1, v 2, ..., v | V |$ , расслабляя каждое исходящее ребро из этой вершины в E_ж. Затем каждая вершина посещается в порядке $v | V |, v | V |-1, ..., v 1$ , расслабляя каждое исходящее ребро из этой вершины в E_б. Каждая итерация основного цикла алгоритма после первой добавляет как минимум два ребра к набору ребер, релаксированные расстояния которых соответствуют правильным расстояниям кратчайшего пути: одно от E_ж и один из E_б. Эта модификация сокращает наихудшее количество итераций основного цикла алгоритма с $| V | - 1$ к ${ displaystyle | V | / 2}$ .^[5]^[6]

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

Примечания

^ ^а ^б ^c ^d Банг-Дженсен и Гутин (2000)
^ Шрайвер (2005)
^ Седжвик (2002).
^ Клейнберг и Тардос (2006).
^ Кормен и др., 2-е изд., Проблема 24-1, стр. 614–615.
^ ^а ^б См. Sedgewick's веб-упражнения за Алгоритмы, 4-е изд., Упражнения 5 и 12 (проверено 30 января 2013 г.).

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

Содержание