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