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

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

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

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

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

Алгоритм

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

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

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

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

Беллман-Форд вбегает $O(|V|\cdot |E|)$ время , где $|V|$ и $|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
        // Initialize the distance to all vertices to infinity
        distance[v] := inf
        // And having a null predecessor
        predecessor[v] := null
    
    // The distance from the source to itself is, of course, zero
    distance[source] := 0

    // 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
            predecessor[v] := u
            // A negative cycle exists; find a vertex on the cycle 
            visited := list of size n initialized with false
            visited[v] := true
            while not visited[u] do
                visited[u] := true
                u := predecessor[u]
            // u is a vertex in a negative cycle, find the cycle itself
            ncycle := [u]
            v := predecessor[u]
            while v != u do
                ncycle := concatenate([v], ncycle)
                v := predecessor[v]
            error "Graph contains a negative-weight cycle", ncycle
    return distance, predecessor

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

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

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

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

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

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

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

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

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

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

Для индуктивного случая сначала докажем первую часть. Рассмотрим момент, когда расстояние вершины обновляется на 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-м ребром. 1 ребер, и затем мы могли бы добавить ребро uv к этому пути, чтобы получить путь с не более чем i ребрами, который строго короче P — противоречие. По индуктивному предположению u.distance после i −1 итераций не превышает длину этого пути от источника до u . Поэтому, uv.weight + u.distance не более длины P . В я ^й итерация, 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. Когда узел получает таблицы расстояний от своих соседей, он вычисляет кратчайшие маршруты ко всем другим узлам и обновляет свою собственную таблицу, чтобы отразить любые изменения.

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

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

Улучшения

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

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

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

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

Ссылки

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

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

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

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