Таким образом, по окончании 3-го шага узлы Д>, Аи А2и А4 имеют постоянные метки, узлы А3пАь временные, а узел А5 никаких меток пока не имеет (рис. 10д).

U2,14>

Рис. 10д

Таблица 3

В таблице 3 указаны длины маршрутов от узла Д>, полученных на первых трех шагах; жирным выделены длины окончательных (т. е. самых коротких) маршрутов.

4-й шаг. Отбираются все узлы, которые соединены с узлом А4 одной дугой и не имеют постоянных меток. Это узлы Аг и А5.

Присваиваем узлу А5 временную метку (ЛЦ, 16).

Сравнивая метки (Аь 19) и (А, 18), замечаем, что расстояние от узла Ао до узла A3 по пути, проходящем через узел Аа, меньше расстояния по пути, проходящем через узел А\. Это наблюдение дает основание заменить метку (Аи 19) на более выгодную метку (А4, 18) (рис. 10е).

Обратимся к узлам, имеющим временные метки, - это узлы А3, А5 и Аь. Сравнивая расстояния от узла Д> до этих узлов, замечаем, что самым коротким будет путь до узла А5. Это означает, что любой другой маршрут из узла Д, в узел А5 будет длиннее.

U2,14>

Рис. 10е

Таким образом, по окончании 4-го шага узлы Д>, Аи А2, А4 и А5 имеют постоянные метки, а узлы А3 и Ав временные (рис. 10ж).

U2,14> Рис. 10ж

Таблица 4

В таблице 4 указаны длины маршрутов от узла Ао, полученных на первых четырех шагах; жирным выделены длины окончательных (т. е. самых коротких) маршрутов.

5-й шаг. Отбираются все узлы, которые соединены с узлом А5 одной дугой и не имеют постоянных меток. Это узел А$.

Сравнивая метки (Ах, 25) и (А5, 22), замечаем, что расстояние от узла Ао до узла Аб по пути, проходящему через узел А5, меньше расстояния по пути, проходящему через узел Ах. Это наблюдение дает основание заменить метку (Аи 25) на более выгодную метку (А5, 22) (рис. Юз).

U2,14>

Рис. Юз

Обратимся к узлам, имеющим временные метки, - это узлы Аъ и Д. Сравнивая расстояния от узла Д> до этих узлов, замечаем, что самым коротким будет путь до узла Ау Это означает, что любой другой маршрут из узла Ао в узел Д* будет длиннее.

Таким образом, по окончании 5-го шага узлы Ао, Аи А2, А3, А4 и А5 имеют постоянные метки, а узел Аь временную метку (рис. 10и).

Таблица 5