Ш А Г 2. Найдем прямое отображение для текущей рассматриваемой вершины: Г(р) = Г(х1) = { х2, х7, х8, х9 }. Все вершины, входящие в прямое отображение имеют временные пометки, поэтому пересчитаем их значение:
L(x2)=min[L(x2),L(x1) + c(x1,x2)]=min[∞,0+10]=10
L(x7)=min[∞,0+3]=3
L(x8)=min[∞,0+6]=6
L(x9)=min[∞,0+12]=12
Ш А Г 3. На данном шаге итерации имеем следующие временные метки вершин:
L(х2) = 10, L(х3) = ∞,
L(х7) = 3, L(х4) = ∞,
L(х8) = 6, L(х5) = ∞,
L(х9) = 12, L(х6) = ∞.
Очевидно, что минимальную метку, равную 3, имеет вершина х7 .
Ш А Г 4. За следующую текущую метку принимаем верши- ну х7 , т. е. p = х7 , а ее метка становится постоянной, L(х7) = 3+ .
Ш А Г 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.