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

Граф с текущими значениями меток вершин показан на рис. 9.3

Рис. 9.3. Пометки в конце первой итерации

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

L(х₂)= min [10, 3 + 2 ] = 5,

L(х₄)= min [ ∞, 3 + 4 ] = 7,

L(х₆)= min [ ∞, 3 + 14 ] = 17,

L(х₉)= min [ 12, 3 + 24 ] = 12.

Ш А Г 3. На данном шаге итерации имеем следующие временные метки вершин:

L(х₂) = 5, L(х₃) = ∞,

L(х₄) = 7, L(х₅) = ∞,

L(х₆) = 17, L(х₈) = 6, L(х₉) = 12.

Очевидно, что минимальную метку, равную 5, имеет вершина х₂.

Ш А Г 4. За следующую текущую метку принимаем вершину х₂, т. е. p = х₂, а ее метка становится постоянной, L(х₂) = 5⁺.

Ш А Г 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.