Пусть колонна автомашин должна доставить груз из пункта 8 в пункт 1. Требуется найти маршрут движения автоколонны минимальной длины.

Ясно, что длины кратчайших маршрутов из узла j в узел 1 и из узла 1 в узел j одинаковы (а последовательности узлов маршрутов взаимно обратны). Будем определять кратчайшие расстояния от узла 1 до каждого из узлов сети j (т.е. следовать против направления стрелок).

Введем следующие обозначения:

d_ij расстояние между смежными узлами i и j (длина дуги Cij).

u_j кратчайшее расстояние между узлами 1 и j, u1 = 0.

Общая формула для вычисления u_j имеет вид: