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

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

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

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

L(х₃) = min [ ∞, 5 + 18 ] = 23,

L(х₉) = min [ 12, 5+13 ] = 12.

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

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

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

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

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

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