Вторая итерация

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

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

Так как вершина X₅ имеет постоянную пометку, то ее не рассматриваем.

l(X₂) = min{l(X₂); l(p) + c(p(X₂))} = min {7, 5+12} = 7

l(X₃) = min{l(X₃); l(p) + c(p(X₃))} = min {∞, 5+11} = 16

l(X₆) = min{l(X₆); l(p) + c(p(X₆))} = min {8, 5+10} = 8

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

min{7, 16, 10, 8} =7 соответствует X₂ => l(X₂*)= 7⁺

p= X₂

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