Из узла 5 (пункт A5): 5-17 (A5-D3); время перевозки 110.

Пункт D2

Построим маршруты в узел 16 (пункт D2) из узлов 1 (пункт А1), 2 (пункт А2), 3 (пункт А3), 4 (пункт А4), 5 (пункт А5).

Приближение k = 0.

Определим время следования по прямым (без посещения промежуточных узлов) маршрутам в узел 16. Для каждого j-го узла (j=5, 7, 9, 12), который соединен дугой с узлом 16 (т.е. имеется прямой маршрут), длина минимального времени следования принимается равной времени следования между этим узлом и узлом 16; для остальных узлов значения принимаются равными бесконечности:

;

;

.

;

Полученные маршруты и значения времён следования по ним занесем в таблицу 5.12 (приложение).

Приближение k = 1.

Определим время следования по возможному маршруту из i-го узла в узел 16 (пункт D2), проходящего через j-й узел, с числом промежуточных узлов не более одного как сумму времени следования от i-го узла до j-го узла и времени следования по прямому маршруту из этого узла в узел 16 (пункт D2):

, i=1,2, …17, j=1,2, …17, i≠16, j≠16, .

В качестве наименьшего времени следования по маршруту из i-го узла в узел 16 принимается минимальное из возможных значений:

.

Полученные маршруты из каждого узла в узел 16 и значения времён следования по ним занесем в таблицу 5.12 (приложение).

Приближение k = 2.

Определим время следования по возможному маршруту из i-го узла в узел 16, проходящему через j-й узел, с числом промежуточных узлов не более двух, как сумму времени следования от i-го узла до j-го узла и времени следования по маршруту из j-го узла в узел 16 с числом узлов не более одного: , i=1,2,…17, j=1,2,…17, i≠16, j≠16, i≠j.

В качестве минимального времени следования по маршруту из i-го узла в узел 16 принимается минимальное значение из возможных:

.

Полученные маршруты из каждого узла в узел 16 и значения времён следования по ним занесем в таблицу 5.12 (приложение).

Приближение k=3.

Определим время следования по возможному маршруту из i-го узла в узел 16, проходящему через j-й узел, с числом промежуточных узлов не более трех как сумму времени следования от i-го узла до j-го узла и времени следования по маршруту из j-го узла в узел 16 с числом узлов не более двух: