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

Алгоритм Беллмана Форда (нахождение кратчайшего расстояния между вершинами графа с отрицательными весами)

Для примера рассмотрим ориентированный граф с отрицательными весами вида:

граф с отрицательными весами

Требуется найти кратчайший путь из вершины 1 в вершину 6

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

Оставшимся вершинам – бесконечно большое число ∞.

инициализация графа

(1,2) (1,3) (2,4) (2,5) (3,2) (3,5) (4,5) (4,6) (5,6)

Первая итерация

Шаг 1

Первая итерация

Шаг 2

граф шаг 2

Шаг 3

граф шаг 3

Шаг 4

граф шаг 4

Шаг 5

граф шаг 5

Вторая итерация

Шаг 1

Вторая итерация

Шаг 2

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

Шаг 3

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

Шаг 4

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

Шаг 5

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

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

1→3→2→5→6

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

if d[u]+s[u,v]<d[v] then d[v]=d[u]+s[u,v]

Leave a Reply

Ваш e-mail не будет опубликован.