Граф с текущими значениями меток вершин показан на рис. 9.3
Рис. 9.3. Пометки в конце первой итерации
Ш А Г 2. Находим Г(х7) = { х2, х4, х6, х9}. Метки всех вершин временные, следовательно пересчитываем их значения:
L(х2)= min [10, 3 + 2 ] = 5,
L(х4)= min [ ∞ , 3 + 4 ] = 7,
L(х6)= min [ ∞ , 3 + 14 ] = 17,
L(х9)= min [ 12, 3 + 24 ] = 12.
Ш А Г 3. На данном шаге итерации имеем следующие временные метки вершин:
L(х2) = 5, L(х3) = ∞ ,
L(х4) = 7, L(х5) = ∞ ,
L(х6) = 17, L(х8) = 6, L(х9) = 12.
Очевидно, что минимальную метку, равную 5, имеет вершина х2 .
Ш А Г 4. За следующую текущую метку принимаем вершину х2 , т. е. p = х2 , а ее метка становится постоянной, L(х2) = 5+ .
Ш А Г 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.