Условие задачи
Применение метода динамического программирования:
Пусть колонна автомашин должна доставить груз из пункта 8 в пункт 1.
Требуется найти маршрут движения автоколонны минимальной длины.
Ответ
Ясно, что длины кратчайших маршрутов из узла j в узел 1 и из узла 1 в узел j одинаковы (а последовательности узлов маршрутов взаимно обратны). Будем определять кратчайшие расстояния от узла 1 до каждого из узлов сети j (т.е. следовать против направления стрелок).
Введем следующие обозначения:
dij расстояние между смежными узлами i и j (длина дуги Cij).
uj кратчайшее расстояние между узлами 1 и j, u1 = 0.
Общая формула для вычисления uj имеет вид:
Потяни
