Первая итерация

Шаг 2. Определим соответствие Г(р) и обновим временные пометки вершин, входящих в это соответствие.

Г(p) = Г(X₅) = {X₁, X₂, X₄, X₆}

обновляем пометки вершин X₁, X₂, X₄, X₆

l(X₁) = min{l(X₁); l(p) + c(p(X₁))} = min {∞, 0+5} = 5

l(X₂) = min{l(X₂); l(p) + c(p(X₂))} = min {∞, 0+7} = 7

l(X₄) = min{l(X₄); l(p) + c(p(X₄))} = min {∞, 0+10} = 10

l(X₆) = min{l(X₆); l(p) + c(p(X₆))} = min {∞, 0+8} = 8

Шаг 3. Выберем минимальную пометку из всех временных, сделаем ее постоянной и присвоим «р» номер, соответствующий этой вершине

min{5, 7, ∞, 10, 8} = 5 соответствует Х₁=> l(X₁*)= 5⁺

p= X₁

Так как не все вершины имеют постоянные пометки, то переходим к следующей итерации