Пример. Рассмотрим сеть с выделенным узлом Aq, заданную на рис. Ю, и найдем кратчайшие маршруты, ведущие по дугам сети от этого выделенного узлам ко всем остальным узлам сети.

Прямой ход

1-й шаг. Все узлы, соединенные с выделенным узлом Aq одной дугой, это узлы А2 и Аз, метятся так, как показано на рис. 10а - число в метке равно расстоянию от помеченного узла до узла Aq. Эти метки (Aq, 15) и (Aq, 10) временные.

Uo,15>

Рис. 10а

Дуга, связывающая узлы Aq и А2, является самой короткой. Это, в частности, означает, что любой маршрут от узла Aq к узлу А2, отличный от дуги AqA2, будет длиннее. Тем самым, выбранная дуга определяет самый короткий путь от узла Aq к узлу А2. Кратчайшее расстояние от узла Aq до узла А2 найдено, и метка (Aq, 10) узла А2 объявляется постоянной.

При получении постоянной метки узел А2 выделяется так же, как и узел Ао. Дуга AqA2 выделяется жирной линией (рис. 106).

Таким образом, по окончании 1-го шага узлы Aq и А2 имеют постоянные метки.

Таблица 1

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

Uo,15>

Рис. 106

2-й шаг. Отбираются все узлы, не имеющие постоянных меток, которые можно соединить с узлами Д> и А2 одной дугой. Это узлы Ai и А4.

Сравнивая длины маршрутов AqA{ и AqA2Au замечаем, что длина первого (15) больше длины второго, 15 > 10 + 3. Поэтому временная метка (Д), 15) узла Ах меняется на метку (А2, 13) (рис. 10в).

U2,13>

С42,14>

Рис. Юв

В этой метке число 13 равно длине пути АА2АХ от узла Д> до узла Аи а А2 - узел на этом пути, предшествующий узлу А\. Узел Аа получает временную метку (А2, 14).

Маршрут AqA2Au связывающий узлы Aq и Аи определяет кратчайшее расстояние от узла Aq к узлу Ах (любой другой маршрут от узла Aq к узлу А\ оказывается длиннее). Поэтому узлу А\ дается постоянная метка (Аъ 13); выделяется и дуга А2А{.

Таким образом, по окончании 2-го шага узлы Aq, А{ и А2 имеют постоянные метки, узел А4 - временную метку (А2,14), а узлы Аъ, А5иАв никаких меток не имеют (рис. Юг).

U2,13>

U2,14>

Рис. Юг

Таблица 2

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

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

Узел А3 получает временную метку (Аи 19), а узел А6 временную метку (А{, 25).

Среди узлов с временными метками выбираем узел, расстояние которого от узла Aq является наименьшим. Это узел а4. Присваиваем его метке (А2, 14) статус постоянной.