double arrow

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


Шаг 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.


Сейчас читают про: