Третья итерация

Шаг 2. G(p) = G(x₂) = {x₁, x₃, x₇, x₉}. Только вершины x₃ и x₉ имеют временные пометки. Из (2) получаем: l(x₃) = min(¥, 5⁺ +18) = 23, аналогично l(x₉) = 12.

Шаг 3. min(23, 7, 17, 6, 12, ¥) = 6,

x₃ x₄ x₆ x₈ x₉ x₅

соответственно x₈ получает постоянную пометку l(x₈) = 6⁺, p = x₈.

Шаг 4. Перейти к шагу 2 (рис. 2.41).

Продолжая итерационный процесс, получим в итоге постоянные пометки для всех вершин графа (рис.2.42) и кратчайшие пути от вершины x₁ ко всем остальным вершинам. Эти пути выделены на рис. 2.42 жирными линиями.

Для нахождения кратчайшего пути между вершиной x₂ и начальной вершиной x₁, последовательно используем соотношение

l(x_i¢) + C(x_i¢_, x_i) = l(x_i). Полагая i = 2 находим вершину x₂¢, непосредственно предшествующей x₂ в кратчайшем пути от x₁ к x₂:

l(x₂¢) + C(x₂¢_, x₂) = l(x₂) = 5. Этому соотношению удовлетворяет вершина x₇. Следовательно, x₂¢ = x₇. Полагая i = 7 и применяя соотношение еще раз, получим x₇¢ = x₁¢. Поэтому кратчайший путь состоит из вершин x₁, x₇, x₂. Аналогичным образом находим все кратчайшие пути от x₁ к остальным вершинам.