Восьмая итерация

Ш А Г 2. Находим Г(х₆) = { х₃, х₅, х₇, х₈, х₉ }. Метка вершины х₃ временная, следовательно, пересчитываем ее значение:

L(х₃) = min [ 23, 17 + 20 ] = 23.

Ш А Г 3. На данном шаге итерации имеем одну временную метку вершины: L(х₃) = 23, которая становится постоянной.

Ш А Г 4. Все вершины имеют постоянные метки, поэтому алгоритм окончен.

Для нахождения кратчайшего пути между вершинами, например, х₂ и начальной х₁ последовательно используем соотношение (**): L(x^'₂)+c(x^'₂,x₂)=L(x₂)=5, где вершина x^'₂ – это вершина, непосредственно предшествующая х₂ в кратчайшем пути от х₁ к х₂.

Единственной такой вершиной является вершина х₇. Далее соотношение (**) применяем второй раз:

L(x₇')+ с(x₇’, x₇) = L(x₇) = 3

Единственной такой вершиной является вершина х₁. Поэтому кратчайший путь от х₁ к х₂ есть (х₁, х₇, х₂). Вершина х₁, называемая базой и дающая все кратчайшие пути от х₁ представляет дерево.

Рис. 9.5.