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