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

Алгоритм Форда – Беллмана нахождения минимального пути

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

Предполагается, что ориентированный граф не содержит контуров отрицательной длины.

Алгоритм 3.1 (Алгоритм Форда – Беллмана).

Основными вычисляемыми величинами этого алгоритма являются величины lj(k), где i = 1, 2, … , n (n – число вершин графа); k = 1, 2, … , n – 1.

Для фиксированных i и k величина lj(k) равна длине минимального пути, ведущего из заданной начальной вершины х1в вершину хi и содержащего не более k дуг.

Шаг 1. Установка начальных условий.

Ввести число вершин графа n и матрицу весов C = (cij).

Шаг 2. Положить k = 0. Положить li(0) = ¥ для всех вершин, кроме х1; положить l1(0) = 0.

Шаг 3. В цикле по k, k = 1,…, n – 1, каждой вершине xi на k-ом шаге приписать индекс li(k) по следу­ющему правилу:

li(k) = {lj(k – 1)+ cji} (3.1)

для всех вершин, кроме х1, положить l1(k) = 0.

В результате работы алгоритма формируется таблица индексов li(k), i = 1, 2, … , n, k = 0, 1, 2, … , n – 1. При этом li(k) определяет длину минимального пути из первой вершины в i-ую, содержащего не более k дуг.

Шаг 5. Восстановление минимального пути.

Для любойвершины xs предшествующая ей вершина xr определяется из соотношения:

lr(n – 2) + crs = ls(n – 1), xrÎ G-1(xs), (3.2)

где G-1(xs)прообраз вершины xs.

Для найденной вершины xr предшествующая ей вершина xq определяется из соотношения:

lq(n – 3) + cqr = lr(n – 2), xqÎ G-1(xr),

где G-1(xr)прообраз вершины xr, и т. д.

Последовательно применяя это соотношение, начиная от последней вершины xi , найдем минимальный путь.

Пример 3.15.

С помощью алгоритма 3.1 найдем минимальный путь из верши­ны х1 в вершину х3 в графе, изображенном на рис. 3.10.

Рис. 3.10

Рассмотрим подробно работу алгоритма Форда – Беллмана для этого примера. Значения индексов li(k) будем заносить в таблицу индексов (табл. 3.1).

Шаг 1. Введем число вершин графа n =5. Матрица весов этого графа имеет вид:

C = .

Шаг 2. Положим k = 0, l1(0) = 0, l2(0) = l3(0) = l4(0) = l5(0) = ¥. Эти значения занесем в первый столбец табл. 3.1.

Шаг 3.

k = 1.

l1(1) = 0.

Равенство (7.1) для k = 1 имеет вид:

li(1) = {lj(0) + cji}.

l2(1) = min{l1(0) + c12; l2(0) + c22; l3(0) + c32; l4(0) + c42; l5(0) + c52;} = min{0 + 1; ¥ + ¥; ¥ + ¥; ¥ + ¥; ¥ + ¥} = 1.

l3(1) = min{l1(0) + c13; l2(0) + c23; l3(0) + c33; l4(0) + c43; l5(0) + c53;} = min{0 + ¥ ; ¥ + 8; ¥ + ¥; ¥ + 2; ¥ + ¥} = ¥ .

l4(1) = min{l1(0) + c14; l2(0) + c24; l3(0) + c34; l4(0) + c44; l5(0) + c54;} = min{0 + ¥ ; ¥ + 7; ¥ + 1; ¥ + ¥; ¥ + 4} = ¥ .

l5(1) = min{l1(0) + c15; l2(0) + c25; l3(0) + c35; l4(0) + c45; l5(0) + c55;} = min{0 + 3; ¥ + 1; ¥ – 5; ¥ + ¥; ¥ + ¥} = 3.

Полученные значения li(1) занесем во второй столбец табл. 3.1. Убеждаемся, что второй столбец, начиная со второго элемента, совпадает с первой строкой матрицы весов, что легко объясняется смыслом величин li(1), которые равны длине минимального пути из первой вершины в i-ую, содержащего не более одной дуги.

k = 2.

l1(2) = 0.

Равенство (3.1) для k = 2 имеет вид:

li(2) = {lj(1) + cji}.

l2(2) = min{0 + 1; 1 + ¥; ¥ + ¥; ¥ + ¥; 3 + ¥} = 1.

l3(2) = min{0 + ¥ ; 1 + 8; ¥ + ¥; ¥ + 2; 3 + ¥} = 9 .

l4(2) = min{0 + ¥ ; 1 + 7; ¥ + 1; ¥ + ¥; 3 + 4} = 7 .

l5(2) = min{0 + 3; 1 + 1; ¥ – 5; ¥ + ¥; 3 + ¥} = 2.

Полученные значения li(2) занесем в третий столбец табл. 3.1. Величины li(2) равны длине минимального пути из первой вершины в i-ую, содержащего не более двух дуг.

k = 3.

l1(3) = 0.

Равенство (3.1) для k = 3 имеет вид:

li(3) = {lj(2) + cji}.

l2(3) = min{0 + 1; 1 + ¥; 9 + ¥; 7 + ¥; 2 + ¥} = 1.

l3(3) = min{0 + ¥ ; 1 + 8; 9 + ¥; 7 + 2; 2 + ¥} = 9 .

l4(3) = min{0 + ¥ ; 1 + 7; 9 + 1; 7 + ¥; 2 + 4} = 6 .

l5(3) = min{0 + 3; 1 + 1; 9 – 5; 7 + ¥; 2 + ¥} = 2.

Полученные значения li(3) занесем в четвертый столбец табл. 3.1. Величины li(3) равны длине минимального пути из первой вершины в i-ую, содержащего не более трех дуг.

k = 4.

l1(4) = 0.

Равенство (3.1) для k = 4 имеет вид:

li(4) = {lj(3) + cji}.

l2(4) = min{0 + 1; 1 + ¥; 9 + ¥; 6 + ¥; 2 + ¥} = 1.

l3(4) = min{0 + ¥ ; 1 + 8; 9 + ¥; 6 + 2; 2 + ¥} = 8 .

l4(4) = min{0 + ¥ ; 1 + 7; 9 + 1; 6 + ¥; 2 + 4} = 6 .

l5(4) = min{0 + 3; 1 + 1; 9 – 5; 6 + ¥; 2 + ¥} = 2.

Полученные значения li(4) занесем в пятый столбец табл. 3.1. Величины li(4) равны длине минимального пути из первой вершины в i-ую, содержащего не более четырех дуг.

Таблица 3.1

I (номер вершины)li(0) li(1) li(2) li(3) li(4)
0 0 0 0 0 ¥ 1 1 1 1 ¥ ¥ 9 9 8 ¥ ¥ 7 6 6 ¥ 3 2 2 2

Шаг 5. Восстановление минимального пути.

Для последней вершины x3предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =3:

lr(3) + cr3 = l3(4), xrÎ G-1(x3), (3.3)

где G-1(x3)прообраз вершины x3.

G-1(x3)= {x2, x4}.

Подставим в (3.3) последовательно r = 2 и r = 4, чтобы определить, для какого r это равенство выполняется:

l2(3) + c23 = 1 + 8 ¹ l3(4) = 8,

l4(3) + c43 = 6 + 2 = l3(4) = 8.

Таким образом, вершиной, предшествующей вершине x3, является вершина x4.

Для вершины x4предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =4:

lr(2) + cr4 = l4(3), xrÎ G-1(x4), (3.4)

где G-1(x4)прообраз вершины x4.

G-1(x4)= {x2, x3, x5}.

Подставим в (3.4) последовательно r = 2, r = 3 и r = 5, чтобы определить, для какого r это равенство выполняется:

l2(2) + c24 = 1 + 7 ¹ l4(3) = 6,

l3(2) + c34 = 1 + 1 ¹ l4(3) = 6,

l5(2) + c54 = 2 + 4 = l4(3) = 6,

Таким образом, вершиной, предшествующей вершине x4, является вершина x5.

Для вершины x5предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =5:

lr(1) + cr5 = l5(2), xr G-1(x5), (3.5)

где G-1(x5)прообраз вершины x5.

G-1(x5)= {x1, x2}.

Подставим в (3.5) последовательно r = 1 и r = 2, чтобы определить, для какого r это равенство выполняется:

l1(1) + c15 = 0 + 3 ¹ l5(2) = 2,

l2(1) + c25 = 1 + 1 = l5(2) = 2,

Таким образом, вершиной, предшествующей вершине x5, является вершина x2.

Для вершины x2предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =2:

lr(0) + cr2 = l2(1), xr G-1(x2), (3.6)

где G-1(x2)прообраз вершины x2.

G-1(x2)= {x1}.

Подставим в (3.6) r = 1, чтобы определить, выполняется ли это равенство:

l1(0) + c12 = 0 + 1 = l2(1) = 1.

Таким образом, вершиной, предшествующей вершине x2, является вершина x1.

Итак, найден минимальный путь – x1, x2, x5, x4, x3, его длина равна 8.

Не нашли то, что искали? Воспользуйтесь поиском:

Источник: https://studopedia.ru/4_22201_algoritm-forda--bellmana-nahozhdeniya-minimalnogo-puti.html

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

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

Определение 1

Алгоритм Форда-Беллмана — это алгоритм поиска кратчайшего пути во взвешенном графе.

Предположим, есть ориентированный взвешенный граф G, который имеет n вершин и m рёбер, и определена некая вершина v. Необходимо определить длины самых коротких путей от вершины v до каждой другой вершины. Данный алгоритм может применяться и к графам, которые имеют рёбра с отрицательным весом, что отличает его от алгоритма Дейкстра.

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

Правда, есть возможность модификации данного алгоритма, и тогда он будет давать сообщение о присутствии цикла, имеющего отрицательный вес, или, более того, выводить данный цикл.

Алгоритм назван в честь учёных из США Ричарда Беллмана и Лестера Форда.

Изобретателем основ этого алгоритма по факту является Форд, который вывел его в середине прошлого века при работе с иной математической задачей, в одной из подзадач которой нужно было определить самый короткий путь в графе. Тогда Форд сделал эскиз алгоритма решения такой задачи.

А чуть позже Беллман выпустил статью, которая была посвящена именно проблеме определения наикратчайшего пути. В своей работе он дал чёткую и однозначную формулировку алгоритма, и она актуальна и по сей день.

Ничего непонятно?

Попробуй обратиться за помощью к преподавателям

Предполагается, что граф не имеет циклов с отрицательным весом. Зададим массив расстояний d[0…n – 1], который по завершению выполнения алгоритма содержит итоговый результат. Сначала заполним массив такими данными: d[v] = 0, а другие элементы d[] будут определены как имеющие размер бесконечность.

Непосредственно алгоритм Форда-Беллмана состоит из нескольких фаз. Во всех фазах выполняется просмотр всех рёбер графа, и согласно алгоритма делается попытка релаксации (rеlax, ослабления) по направлению каждого ребра (а, b) стоимости с. Релаксация вдоль ребра означает попытку улучшения значения d[b] за счёт значения d[а] + с.

По факту это означает попытку улучшения результата для вершины b, используя ребро (а, b) и действующий ответ для вершины a. Заявлено, что хватит n – 1 фазы алгоритма для правильного подсчёта длин всех самых коротких путей в графе (конечно, без циклов с отрицательным весом).

Если вершины являются недостижимыми, то дистанция d [] для них так и остаётся бесконечной.

Простая реализация алгоритма

В алгоритме Форда-Беллмана удобнее представить граф как один список всех рёбер, а не n штук, как делается в некоторых других алгоритмах графов. В программе, представленной ниже, определяется структура данных edge для рёбер.

В качестве входных данных алгоритма выступают числа n, m, списки рёбер e, а также нумерация вершины старта v. Нумерация вершин идёт от нуля до n – 1. INF — это обозначение константы с размерностью «бесконечность».

Она должна быть подобрана так, чтобы всегда была больше всех вероятных длин путей.

Рисунок 1. Простая реализация алгоритма. Автор24 — интернет-биржа студенческих работ

Выполнение проверки «if (d[e[j].a] < INF)" необходимо только в случае, если у графа есть рёбра с отрицательным весом. Если эту проверку не выполнять, то возможны релаксации из вершин, до которых не определены пока пути, и появление некорректных расстояний.

Улучшенная реализация алгоритма

Работу алгоритма возможно сделать более быстрой. Часто итоговый результат может быть найден лишь за незначительное число фаз, а остальные фазы работы алгоритма по сути бесполезны и в них в холостую ведётся просмотр остальных рёбер.

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

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

Рисунок 2. Улучшенная реализация алгоритма. Автор24 — интернет-биржа студенческих работ

Восстановить пути

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

С этой целью создадим добавочный массив р[0…n – 1], который будет служить для сохранения истории, то есть предыдущую вершину в самом коротком маршруте, который ведёт к ней.

То есть, самый короткий путь к какой-либо вершине а будет самым коротким маршрутом до какой-либо вершины р[a], к которому добавили в окончание вершину а. Следует отметить, что действие алгоритма Форда-Беллмана следует этой же логической цепи.

Алгоритм, полагая, что самый короткий маршрут до одной вершины уже вычислен, делает попытку уменьшить (улучшить) самый короткий маршрут до следующей вершины. Таким образом, при улучшении необходимо просто сохранить в массиве р [], какая вершина вызвала это улучшение.

Вначале выполняется проход по ранее пройденным вершинам, с началом в вершине t, и весь маршрут сохраняется в переменной path. В этой переменной (списке) и будет самый короткий путь.

Доказательство алгоритма

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

Можно доказать, что, когда будут исполнены i фаз алгоритма, будут правильно определены все оптимальные маршруты, которые по длине (по количеству рёбер) не будут превосходить i.

Или по-другому, для каждой вершины а будем считать, что К это количество рёбер в самом коротком маршруте к ней. То есть это означает, что после К фаз самый короткий маршрут будет с гарантией определён.

Источник: https://spravochnick.ru/informatika/algoritmizaciya/algoritm_forda-bellmana/

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

Алгоритм Форда-Беллмана
В преддверии старта курса «Алгоритмы для разработчиков» подготовили очередной перевод интересной статьи.

Задача: Дан граф и начальная вершина src в графе, необходимо найти кратчайшие пути от src до всех вершин в данном графе.

В графе могут присутствовать ребра с отрицательными весами.

Мы уже обсуждали алгоритм Дейкстры в качестве способа решения этой задачи. Алгоритм Дейкстры является жадным алгоритмом, а его сложность равна O(VLogV) (с использованием кучи Фибоначчи).

Однако Дейкстра не работает для графов с отрицательными весами ребер, тогда как Беллман-Форд — вполне. Алгоритм Беллмана-Форда даже проще, чем алгоритм Дейкстры, и хорошо подходит для распределенных систем.

В то же время сложность его равна O(VE), что больше, чем показатель для алгоритма Дейкстры.

Рекомендация: Прежде, чем двигаться к просмотру решения, попробуйте попрактиковаться самостоятельно.

Ниже приведены подробно расписанные шаги.

Входные данные: Граф и начальная вершина src.

Выходные данные: Кратчайшее расстояние до всех вершин от src. Если попадается цикл отрицательного веса, то самые короткие расстояния не вычисляются, выводится сообщение о наличии такого цикла.

  1. На этом шаге инициализируются расстояния от исходной вершины до всех остальных вершин, как бесконечные, а расстояние до самого src принимается равным 0. Создается массив dist[] размера |V| со всеми значениями равными бесконечности, за исключением элемента dist[src], где src — исходная вершина.
  2. Вторым шагом вычисляются самые короткие расстояния. Следующие шаги нужно выполнять |V|-1 раз, где |V| — число вершин в данном графе.
    • Произведите следующее действие для каждого ребра u-v:
      Если dist[v] > dist[u] + вес ребра uv, то обновите dist[v]
      dist [v] = dist [u] + вес ребра uv
  3. На этом шаге сообщается, присутствует ли в графе цикл отрицательного веса. Для каждого ребра u-v необходимо выполнить следующее:
    • Если dist[v] > dist[u] + вес ребра uv, то в графе присутствует цикл отрицательного веса.

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

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

Затем он вычисляет кратчайшие пути длиной не более двух ребер и так далее. После i-й итерации внешнего цикла вычисляются кратчайшие пути длиной не более i ребер.

В любом простом пути может быть максимум |V|-1 ребер, поэтому внешний цикл выполняется именно |V|-1 раз.

Идея заключается в том, что если мы вычислили кратчайший путь с не более чем i ребрами, то итерация по всем ребрам гарантирует получение кратчайшего пути с не более чем i + 1 ребрами (доказательство довольно простое, вы можете сослаться на эту лекцию или видеолекцию от MIT)

Давайте разберемся в алгоритме на следующем примере графа. Изображения взяты отсюда.
Пусть начальная вершина равна 0. Примите все расстояния за бесконечные, кроме расстояния до самой src. Общее число вершин в графе равно 5, поэтому все ребра нужно пройти 4 раза. Пусть ребра отрабатываются в следующем порядке: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D). Мы получаем следующие расстояния, когда проход по ребрам был совершен первый раз. Первая строка показывает начальные расстояния, вторая строка показывает расстояния, когда ребра (B, E), (D, B), (B, D) и (A, B) обрабатываются. Третья строка показывает расстояние при обработке (A, C). Четвертая строка показывает, что происходит, когда обрабатываются (D, C), (B, C) и (E, D). Первая итерация гарантирует, что все самые короткие пути будут не длиннее пути в 1 ребро. Мы получаем следующие расстояния, когда будет совершен второй проход по всем ребрам (в последней строке показаны конечные значения). Вторая итерация гарантирует, что все кратчайшие пути будут иметь длину не более 2 ребер. Алгоритм проходит по всем ребрам еще 2 раза. Расстояния минимизируются после второй итерации, поэтому третья и четвертая итерации не обновляют значения расстояний. Реализация: # Python program for Bellman-Ford's single source # shortest path algorithm. from collections import defaultdict # Class to represent a graph class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = [] # default dictionary to store graph # function to add an edge to graph def addEdge(self, u, v, w): self.graph.append([u, v, w]) # utility function used to print the solution def printArr(self, dist): print(«Vertex Distance from Source») for i in range(self.V): print(«% d \t\t % d» % (i, dist[i])) # The main function that finds shortest distances from src to # all other vertices using Bellman-Ford algorithm. The function # also detects negative weight cycle def BellmanFord(self, src): # Step 1: Initialize distances from src to all other vertices # as INFINITE dist = [float(«Inf»)] * self.V dist[src] = 0 # Step 2: Relax all edges |V| — 1 times. A simple shortest # path from src to any other vertex can have at-most |V| — 1 # edges for i in range(self.V — 1): # Update dist value and parent index of the adjacent vertices of # the picked vertex. Consider only those vertices which are still in # queue for u, v, w in self.graph: if dist[u] != float(«Inf») and dist[u] + w < dist[v]: dist[v] = dist[u] + w # Step 3: check for negative-weight cycles. The above step # guarantees shortest distances if graph doesn't contain # negative weight cycle. If we get a shorter path, then there # is a cycle. for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: print "Graph contains negative weight cycle" return # print all distance self.printArr(dist) g = Graph(5) g.addEdge(0, 1, -1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, -3) # Print the solution g.BellmanFord(0) # This code is contributed by Neelam Yadav

Выходные значения:

Примечания:

  1. Отрицательные веса встречаются в различных применениях графов. Например, вместо того чтобы увеличивать стоимость пути, мы можем получить выгоду, следуя по определенному пути.
  2. Алгоритм Беллмана-Форда работает лучше для распределенных систем (лучше, чем алгоритм Дейкстры). В отличие от Дейкстры, где нам нужно найти минимальное значение всех вершин, в Беллмане-Форде ребра рассматриваются по одному.

Упражнения:

  1. Стандартный алгоритм Беллмана-Форда сообщает кратчайшие пути только в том случае, если в нем нет циклов отрицательного веса. Измените его таким образом, чтобы он сообщал о кратчайших путях даже при наличии такого цикла.
  2. Можем ли мы использовать алгоритм Дейкстры для поиска кратчайших путей в графе с отрицательными весами? Есть такая идея: вычислить минимальное значение веса, прибавить положительное значение (равное модулю значения минимального веса) ко всем весам и запустить алгоритм Дейкстры для модифицированного графа. Сработает ли такой алгоритм?

Простая реализация алгоритма Беллмана-Форда

Источники:

www..com/watch?v=Ttezuzs39nk

en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
www.cs.arizona.edu/classes/cs445/spring07/ShortestPath2.prn.pdf

Источник: https://habr.com/ru/company/otus/blog/484382/

Booksm
Добавить комментарий