В транспортной сети (рис. 2) имеется несколько маршрутов по проезду из начального пункта 1 в конечный пункт 11. Стоимость проезда между отдельными пунктами транспортной сети представлена в соответствующей

Уравнение Беллмана.

F_к(S) = min(t_sj + F_k-1(j))

S пункт отправления, j - пункт назначения, t_sj стоимость проезда отправления в пункт назначения.

Функция Беллмана минимально возможные затраты по перемещению из 1-го в 11-й пункт. Задачу начинаем решать с конца.

1 шаг. F₁( S ) = t_s11

Из пункта 11 можно попасть в пункты 8, 9, 10 при этом расстояния до этих пунктов 7, 6, 10 берутся из рис.1, третий столбец табл. 1 определяется по формуле на 1-м шаге, а j * - в каком пункте достигается минимальное значение.

Таблица 1