Третья итерация

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

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

Так как вершины X₁ и X₅ имеет постоянные пометки, то их не рассматриваем.

l(X₃) = min{l(X₃); l(p) + c(p(X₃))} = min {16, 7+6} = 13

l(X₄) = min{l(X₄); l(p) + c(p(X₄))} = min {10, 7+3} = 10

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

min{13, 10, 8} = 8 соответствует X₆=> l(X₆*) = 4⁺

p= X₆

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