Алгоритм Форда-Беллмана - Сложные системы и ИИ

Контенус

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

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

Условия.

Общий случай

Первоначально расстояние инициализируется равным 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: Луки (а₅,а₂) и (а₅,а₄) расслаблены, мы обновляем расстояния и предшественников.

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

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

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

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

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

Итерация	1	2	3	4	5
0	ниже	ниже	ниже	ниже	0
1	ниже	4(5)	ниже	2(5)	0
2	7(2)	3(4)	3(4)	2(5)	0
3	6(2)	3(4)	3(4)	2(5)	0
4	6(2)	3(4)	3(4)	2(5)	0

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