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

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

Задача о кратчайших путях из начала координат имеет решение только в том случае, если нет достижимой схемы стока. Алгоритм Форда-Беллмана проверяет, что из с. Если это так, он возвращает кратчайшие пути из с. L’algorithme de Ford-Bellman est un алгоритм из динамическое программирование gourmand qui calcule les chemins les plus courts de taille croissante. Il convient à n’importe quel график.

Условия.

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

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

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

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

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

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

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

Le chemin le plus court de l’origine à lui-même est de 0. Puis les chemins de taille 1 sont calculés de telle sorte que nous ne gardons que le кратчайший путь de l’origine à tout autre sommet.

алгоритм вычисляет кратчайшие пути путей размера 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 такие блоггеры, как: