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