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