Шаг 2. G(p) = G(x1) = {x2, x7, x8, x9}.Все эти вершины имеют временные пометки.
Таблица 2.4 – Матрица смежности с весами для графа на рис. 2.38
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | |
x1 | |||||||||
x2 | |||||||||
x3 | |||||||||
x4 | |||||||||
x5 | |||||||||
x6 | |||||||||
x7 | |||||||||
x8 | |||||||||
x9 |
Уточняем пометки в соответствии с формулой (2).
l(x2) = min(¥, 0+ +10) = 10, аналогично l(x7) = 3, l(x8) = 6, l(x9) = 12.
Шаг 3. min(10, 3, 6, 12, ¥) = 3,
x2 x7 x8 x9 x3, x4, x5, x6
соответственно x7 получает постоянную пометку l(x7) = 3+, p = x7.
Шаг 4. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2. Значения пометок вершин графа приведены на рис. 2.39. Обведены вершины с постоянными пометками.
Вторая итерация.
Шаг 2. G(p) = G(x7) = {x2, x4, x6, x9}.Пометки всех этих вершин временные. Из (2) получим l(x2) = 5, l(x4) =7, l(x6) = 17, l(x9) = 12.
Шаг 3. min(5, 7, 17, 6, 12, ¥) = 5,
x2 x4 x6 x8 x9 x3, x5
соответственно x2 получает постоянную пометку. l(x2) = 5+, p = x2.
Шаг 4. Перейти к шагу 2. Значения пометок приведены на рис. 2.40.