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

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

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

Условия.

  • Общий случай

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

Алгоритм кратчайшего пути Форда-Беллмана

Мы проверим все дуги и по возможности улучшим значение путей. Новое значение для каждой вершины — это минимальное расстояние всех путей размера k-1 плюс ребра, входящие в вершину. Поскольку могут быть схемы, вы должны начать сначала.

Алгоритм кратчайшего пути Форда-Беллмана
Алгоритм кратчайшего пути Форда-Беллмана

По практическим причинам решение алгоритма Форда-Беллмана возвращает только вектор. Что соответствует текущему столбцу представленной таблицы.

Оптимальность.

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

алгоритм вычисляет кратчайшие пути путей размера k (для итерации k) из кратчайших путей путей размера k-1, поэтому он оптимален вне зависимости от останавливающей итерации алгоритма.

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

за каждый вершина u графа d[u, 0] = +∞ d[s, 0] = 0
за к = 1 вплоть до Количество вершин - 1 Сделать
    для каждого arc(u,v) графика Сделать
        d[v, k] := min(d[v, k-1], d[u, k-1] + вес(u, v))
    конец
конец
вернуться из

Пример

Возьмем, к примеру, следующий график:

Алгоритм кратчайшего пути Форда-Беллмана

Возьмем узел 5 в качестве источника, затем инициализируем остальные расстояния до бесконечности. Вектор π представляет предшественников.

Алгоритм кратчайшего пути Форда-Беллмана

Итерация 1: Луки (а5,а2) и (а5,а4) расслаблены, мы обновляем расстояния и предшественников.

Алгоритм кратчайшего пути Форда-Беллмана

Итерация 2: Луки (а2,а1), (а4,а2) и (а4,а3) ослаблены, мы обновляем расстояния до узлов 1, 2 и 4. Обратите внимание, что (а4,а2) находит кратчайший путь к 2 через узел 4.

Алгоритм кратчайшего пути Форда-Беллмана

Итерация 3: Луки (а2,а1) ослаблены (поскольку мы нашли более короткий путь к узлу 2 на последней итерации).

Алгоритм кратчайшего пути Форда-Беллмана

Итерация 4: дуга не ослаблена.

Алгоритм кратчайшего пути Форда-Беллмана

Кратчайшие пути, начинающиеся с узла 5:

Алгоритм кратчайшего пути Форда-Беллмана

Алгоритм представлен в виде таблицы, как показано ниже:

Итерация12345
0нижениженижениже0
1ниже4(5)ниже2(5)0
27(2)3(4)3(4)2(5)0
36(2)3(4)3(4)2(5)0
46(2)3(4)3(4)2(5)0

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

Делиться
ru_RURU
%d такие блоггеры, как: