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

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

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

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

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

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

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

(3.15)

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

Тогда v v_im … v_i2 v – искомый минимальный путь из v в v_j.

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

Рис. 3.32

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

Таблица 3.7

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

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

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

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

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

1≤j≤6

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

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

z = min (z + C ).

1≤j≤6

Минимум правой части этой формулы будет при 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.

1≤j≤6

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

Таблица 3.8

i	z	z	z	z	z	z
1	0	0	0	0	0	0
2			7	5	5	5
3		5	3	3	3	3
4		5	4	4	4	4
5		2	2	2	2	2
6		12	1 2	9	7	7

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

Шаг 2. Определяем минимальное число m ≥ 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 .