logo
tsvpis

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

Формируем массив D[k](i) – минимально возможная стоимость переезда (перехода, перевозки) из вершины v0 в v1 на каждом этапе работы нашего алгоритма.

Первоначально он задается как D[0](i) = (0, , , …, ).

Затем пересчитываем стоимости всех вершин по формуле

(3.1)

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

Пример. Дан граф (рис 3.5). Найти расстояние от нулевой вершины до всех остальных.

Рисунок 3.5 – Исходный граф

Решение:

Рисунок 3.6 – Стоимости переездов из вершины v0

Первоначальный массив стоимостей переходов выглядит так:

D(0)=(0, , , , ). Сосчитаем стоимость вершины i на k-том шаге. В вершину j мы могли попасть из нулевой вершины, из первой вершины и т.д.

Тогда:

D(k+1)(i) = (D(k)(0) + (0,i), D(k)(1) + (1,i), …)

стоимость перехода из вершины 0 в вершину i.

стоимость вершины 0 на предыдущем шаге + стоимость переезда из нулевой вершины в i­-ую.

Стоимость вершины i на каждом шаге считаем по формуле (3.1):

D[k+1](i) = min (D[k](0) + C(0,i), D[k](1) + C(1,i), D[k](2) + C(2,i), D[k](3) + C(3,i), D[k](4) + C(4,i) ).

Вычислим стоимости вершин данного графа на первом шаге:

D[1](1) = min (D[0](0) + C(0,1), D[0](1) + C(1,1), D[0](2) + C(2,1), D[0](3) + C(3,1), D[0](4) + C(4,1) )

= min (0 +25, + 0, + 6, + , + ) = min (25, , , , ) = 25;

D[1](2) = min (D[0](0) + C(0,2), D[0](1) + C(1,2), D[0](2) + C(2,2), D[0](3) + C(3,2), D[0](4) + C(4,2) )

= min (0 +15, + 6, + 0, + 4, + ) = min (15, , , , ) = 15;

D[1](3) = min (D[0](0) + C(0,3), D[0](1) + C(1,3), D[0](2) + C(2,3), D[0](3) + C(3,3), D[0](4) + C(4,3) )

= min (0 +7, + , + 4, + 0, + 3) = min (7, , , , ) = 7;

D[1](4) = min (D[0](0) + C(0,4), D[0](1) + C(1,4), D[0](2) + C(2,4), D[0](3) + C(3,4), D[0](4) + C(4,4) )

= min (0 +2 + , +, + 3, + 0) = min (2, , , , ) = 2;

Вычислим стоимости вершин данного графа на втором шаге:

D[2](1) = min (D[1](0) + C(0,1), D[1](1) + C(1,1), D[1](2) + C(2,1), D[1](3) + C(3,1), D[1](4) + C(4,1) )

= min (0 +25, 25 + 0, 15 + 6, 7 + , 2 + ) = min (25, 25, 21, , ) = 21;

D[2](2) = min (D[1](0) + C(0,2), D[1](1) + C(1,2), D[1](2) + C(2,2), D[1](3) + C(3,2), D[1](4) + C(4,2) )

= min (0 +15, 25 + 6, 15 + 0, 7 + 4, 2 +) = min (15, 31, 15, 11, ) = 11;

D[2](3) = min (D[1](0) + C(0,3), D[1](1) + C(1,3), D[1](2) + C(2,3), D[1](3) + C(3,3), D[1](4) + C(4,3) )

= min (0 +7, 25 + , 15 + 4, 7 + 0, 2 + 3) = min (7, , 21, 7, 5) = 5;

D[2](4) = min (D[1](0) + C(0,4), D[1](1) + C(1,4), D[1](2) + C(2,4), D[1](3) + C(3,4), D[1](4) + C(4,4) )

= min (0 +2, 25 + , 15 + , 7 + 3, 2 + 0) = min (2, , , 10, 2) = 2 – наблюдается стабилизация.

Вычислим стоимости вершин данного графа на третьем шаге:

D[3](1) = min (0 +25, 21 + 0, 11 + 6, 5 + , 2 + ) = min (25, 21, 17, , ) = 17;

D[3](2) = min (0 +15, 21 + 6, 11 + 0, 5 + 4, 2 + ) = min (15, 27, 11, 9, ) = 9;

D[3](3) = min (0 +7, 21 + , 11 + 4, 5 + 0, 2 + 3) = min (7, , 15, 5, 5) = 5 – стабилизация;

D[3](4) = min (0 +2, 21 + , 11 + , 5 + 3, 2 + 0) = min (2, , , 8, 2) = 2 – стабилизация;

Вычислим стоимость вершина данного графа на четвертом шаге:

D[4](1) = min (0 +25, 17 + 0, 9 + 6, 5 + , 2 + ) = min (25, 17, 15, , ) = 15;

D[4](2) = min (0 +15, 17 + 6, 9 + 0, 5 + 4, 2 + ) = min (15, 23, 9, 9, ) = 9 – стабилизация;

D[4](3) = min (0 +7, 17 + , 9 + 4, 5 + 0, 2 + 3) = min (7, , 13, 5, 5) = 5 – стабилизация;

D[4](4) = min (0 +2, 17 + , 9 + , 5 + 3, 2 + 0) = min (2, , , 8, 2) = 2 – стабилизация;

Вычислим стоимости вершин данного графа на пятом шаге:

D[5](1) = min (0 +25, 15 + 0, 9 + 6, 5 + , 2 + ) = min (25, 15, 15, , ) = 15­ – стабилизация;

D[5](2) = min (0 +15, 15 + 6, 9 + 0, 5 + 4, 2 + ) = min (15, 21, 9, 9, ) = 9 – стабилизация;

D[5](3) = min (0 +7, 15 + , 9 + 4, 5 + 0, 2 + 3) = min (7, , 13, 5, 5) = 5 – стабилизация;

D[5](4) = min (0 +2, 15 + , 9 + , 5 + 3, 2 + 0) = min (2, , , 8, 2) = 2 – стабилизация;

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

Оценим трудоемкость алгоритма Форда-Беллмана.

В нем участвуют три цикла: внешний типа While выполняется до тех пор, пока не произошла стабилизация. Следующий по вложенности цикл – по вершинам графа. Самый внутренний цикл (нахождение минимума) – по переменной j. Итого,

T(n) = l·n·n, где l – количество проходов внешнего цикла While.

Так как l ≤ n (потому что самый длинный оптимальный маршрут включает в себя прохождения n-1 вершин, плюс делаем еще один проход, чтобы убедиться в стабилизации), то

2n2 ≤ T(n) ≤ n3.