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

Используя утверждение 1, нетрудно описать алгоритм нахождения таблицы значений величин (будем записывать её в виде матрицы, где - номер строки, - номер столбца). Действительно, используя рекуррентные соотношения (2), (3) и исходя из (1), последовательно определяем набор величин (()-й столбец матрицы), начиная с , а затем шаг за шагом увеличиваем значение до любой необходимой величины.

Алгоритм Форда – Беллмана нахождения минимального пути в нагруженном орграфе из в

Шаг 1. Пусть мы уже составили таблицу величин . Если не достижима из (предполагаем, что все величины конечны). В этом случае работа алгоритма заканчивается.

Шаг 2. Пусть . Тогда число выражает длинны любого минимального пути из в в нагруженном орграфе . Определим минимальное число , при котором выполняется равенство . По определению чисел получим, что - минимальное число дуг в пути среди всех минимальных путей из в в нагруженном орграфе .

Шаг 3. Последовательно определяем номера такие что

. . . . . . (4)

Из (4) с учётом того, что , имеем , откуда, используя (1), получаем

(5)

Складывая равенства (4) и учитывая (5), имеем

т.е. - искомый минимальный путь из в в нагруженном орграфе . Заметим, что в этом пути ровно дуг Следовательно, мы определили путь с минимальным числом дуг среди всех минимальных путей из в в нагруженном орграфе .

Замечание. Номера, удовлетворяющие (4) вообще говоря, могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных путей из вс минимальным числом дуг среди минимальных, путей извв нагруженном орграфе.

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

Пример 83.

Определить минимальный путь из v1 в v6 в нагруженном орграфе D, изображенном на рисунке 35.

Решение.

Составим матрицу C(D) длин дуг нагруженного орграфа D(табл. 68). Справа от матрицы C(D) припишем шесть столбцов, которые будем определять, используя рекуррентное соотношение (2) и исходя из (1).

Величина выражает длину минимального пути из v1 в v6 в нагруженном орграфе D. Найдем минимальное число , при котором выполняется равенство . Получаем, что k1 = 4. Таким образом, минимальное число дуг в пути среди всех минимальных путей из v1 в v6 в нагруженном графе D равняется 4. Определим теперь последовательность номеров i1, i2, i3, i4, i5, где i1 = 6, удовлетворяющих (4) (для этого используем формулу (2)).

Таблица 68

Получаем, что в качестве такой последовательности надо взять номера 6, 2, 3, 5, 1, так как

Тогда v1v5v3v2v6 – искомый минимальный путь из v1 в v6 в нагруженном орграфе D, причем он содержит минимальное число дуг среди всех возможных минимальных путей из v1 в v6 .

Шаг 1. Составляется матрица длин дуг и таблица величин z. Если z = ,

то вершина vj не достижима из v. В этом случае работа алгоритма заканчивается.

Шаг 2. Величина z выражает длину любого минимального пути из v в

vj. Определим минимальное число m e 1, при котором выполняется равенство

z = z. По определению чисел z получаем, что m – минимальное число дуг в пути среди всех минимальных путей из v в vj.

Шаг 3. Последовательно определяем номера i, …, i такие, что

(3.15)

. . . . . . . . . . . . . . .

Тогда v vim … vi2 v – искомый минимальный путь из v в vj.

Пример. Найти минимальный путь в орграфе рис.3.32 из вершины v в вершину v.

Рис. 3.32

Шаг 1. Составляем матрицу длин дуг данного орграфа, которая представлена в табл.3.7.

Таблица 3.7

	v1	v2	v3	v4	v5	v6
v1
v2
v3
v4
v5
v6

Далее составляем таблицу величин z, которая представлена в табл. 3.8. Первый столбец этой таблицы ( k = 0 ) будет состоять из следующих элементов

z = 0, z = z = z = z = z = .

Затем определяем элементы второго столбца ( k = 1 ).

По формулам (3.14) получим

z = min [0, min( z + C)].

1djd6

В этом выражении min (z + C) = , т.к. C = (см. первый столбец табл.3.8). 1djd6

Следовательно, все элементы z = 0, т.е. все элементы первой строки равны 0. Остальные элементы второго столбца определяются формулой (3.13), которая будет иметь вид

z = min (z + C).

1djd6

Минимум правой части этой формулы будет при j = 1 т.к. все z = кроме z = 0. Следовательно, искомые элементы будут вычисляться по формуле

z =C и будут равны z = , z = 5, z = 5, z = 2, z = 12.

Далее по формуле (3.13) вычисляем элементы третьего столбца ( k=2 ), начиная со второго. z = min ( z + C) = 7, z = 3, z = 4, z = 2, z = 12.

1djd6

Аналогично определяем элементы остальных строк.

Таблица 3.8

i	z	z	z	z	z	z





			1 2

Из табл.3.8 видно, что z = 7 ` ., следовательно, вершина v достижима из вершины v.

Шаг 2. Определяем минимальное число m e 1, из равенства z = z.Из табл.3.8 видно, что m = 4, т.е. минимальное число дуг в пути среди всех минимальных путей из вершины v в вершину v равно 4.

Шаг 3. Последовательно из выражений (3.10) определяем номера

i, i, i, i, i.

Первое равенство в (3.15) будет иметь вид

z + C = z = 7.

Сравнивая четвертый столбец табл.3.8 и шестой столбец табл.3.7 видим, что это равенство выполняется при i = 2, т.е.

z + C = 5 + 2 = 7.

Запишем второе равенство из (3.15), которое будет иметь вид

z+ C = z = 5.

Сравнивая третий столбец табл.3.8 и второй столбец табл.3.7 видим, что это равенство выполняется при i = 3, т.е.

z + C = 3 + 2 = 5.

Следующее равенство из (3.15) имеет вид

z + C = z = 3 и выполняется при i = 5.

Последнее равенство будет иметь вид

z + C = z = 2 и выполняется при i = 1.

Тогда искомый минимальный путь из вершины v в вершину v будет следующий v v v v v. Он содержит минимальное число дуг среди всех возможных путей из v в v.