0*2,14)

Рис. 10и

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

б-й шаг. Узел А - последний узел с временной меткой (А5, 22). Она становится постоянной вследствие того, что путь в узел А$, проходящий через узел А3, получивший постоянную метку на предыдущем шаге, имеет ту же длину - 22 и менять ее на новую нецелесообразно.

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

Таблица 6

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

Замечание. На каждом шаге временная метка одного из узлов меняет свой статус на постоянную по следующему правилу: рассматриваются все узлы с временными метками и выбирается тот из них, расстояние до которого от узла Д> является наименьшим.

Обратный ход

Используя вторую компоненту метки, определяем последовательность узлов в каждом кратчайшем маршруте. Например:

метка (А5, 22) узла А$ указывает на предшествующий узел А5, метка (Аа, 16) узла А5 указывает на предшествующий узел Аа, метка (А2, 14) узла А4 указывает на предшествующий узел Аъ метка (Ао, 10) узла А2 указывает на исходный узел Ао. В результате, обратная последовательность узлов кратчайшего маршрута от узла Ао к узлу Аь имеет вид

А6->А5->А4->А2->Ао

Ответ:

Описание алгоритма

Начнем с того, что пометим начальный узел и объявим эту метку постоянной.

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

Временная метка узла на 1-м шаге строится по следующему правилу:

это упорядоченная пара, первый элемент которой - начальный узел (уже имеющий постоянную метку), а второй элемент - число, равное длине дуги, соединяющей этот узел с начальным.

Затем среди всех узлов с временными метками выбираем узел, расстояние которого от начального узла минимально. Если таких узлов несколько, выбираем любой. И объявляем временную метку выбранного узла постоянной.

2-й шаг. Рассмотрим все дуги, исходящие из узлов с постоянными метками (теперь их уже два), и снабдим все узлы, в которые идут эти дуги, временными метками по следующему правилу:

1) если новый узел не был помечен ранее, то временная метка - это упорядоченная пара, первый элемент которой - узел с постоянной меткой, из которого выходит выбранная дуга, а второй элемент - число, равное длине маршрута, ведущего в этот узел по узлам с постоянными метками, считая от начального узла,

2) если же узел уже имел временную метку, необходимо поступить так - сравнить длины старого и нового маршрутов, связывающих этот узел с начальным узлом, и либо заменить прежнюю временную метку на новую (если длина нового маршрута оказалась меньше длины старого), либо оставить ту же временную метку (если это не так).

В результате мы получим новый набор узлов с временными метками. Выберем тот из узлов, длина маршрута до которого от начального узла является наименьшей. Если таких узлов несколько, выбираем любой и объявляем его временную метку постоянной.

Последующие шаги проводятся по тому же правилу, что и 2-й шаг, и заканчиваются присвоением постоянной метки очередному узлу сети. Так как на каждом шаге число узлов с постоянными метками увеличивается на единицу, то, сделав п - 1 шаг (считаем, что в сети п узлов), мы присвоим постоянные метки всем п узлам сети.

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

Обоснование корректности алгоритма

Прежде всего заметим, что после каждого шага итерации временная метка каждого помеченного узла показывает кратчайший маршрут до него от первоначально выделенного узла, в котором предпоследний узел имеет постоянную метку.