Вторая итерация

Шаг 2. G(p) = G(x₇) = {х₂, х₄, х_б, х₉}.Пометки всех этих вершин временные. Из (8) получим: l(х₂) = 5, l(х₄) = 7, l(х₆)=17, l(х₉) = 12.

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

х₂ х₄ х₆ х₈ х₉ х₃, х₅

Вершина х₂ получает постоянную пометку 1(х₂) = 5⁺.

Далее р = x₂.

Шаг 4. Значения пометок приведены на рис. 3.36. Переходим к шагу 2.

 

Рис. 3.36. Пометки в начале третьей итерации

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

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

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

х₃ х₄ х₆ х₈ х₉ х₅

Вершина х₈ получает постоянную пометку 1(х₈) = 6⁺, р=x₈.

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

Рис. 3.37. Пометки в начале четвертой итерации

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

Для нахождения кратчайшего пути между вершиной х₂ и на­чальной вершиной х₁ последовательно используем соотношение l(х_i¢) + С(х_i¢, х_i) = l(х_i). Полагая i = 2 находим вершину х₂', непосред­ственно предшествующей х₂ в кратчайшем пути от х₁ к х₂:

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

Рис. 3.38. Пометки и кратчайшие пути в графе