Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 64 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

ШАГ 2. Находим Г(x
8
) = { x
1
, x
5
, x
6
, x
9
}. Метки вершин x
5
, x
6
и x
9
временные,
следовательно пересчитываем их значения:
L(x
5
) = min [ ∞ , 6+23 ] = 29,
L(x
6
) = min [ 17 , 6+15 ] = 17,
L(x
9
) = min [ 12 , 6+5 ] = 11.
ШАГ 3
. На данном шаге итерации имеем следующие временные метки вершин:
L(x
3
) = 23, L(x
4
) = 7, L(x
5
) = 29, L(x
6
) = 17, L(x
9
) = 11.
Очевидно, что минимальную метку, равную 7 имеет вершина x
4
.
ШАГ 4
. За следующую текущую метку принимаем вершину x
4
, т.е. p = x
4
, а ее
метка становится постоянной,
L(x
4
) = 7
+
ШАГ 5
. Так как не все вершины графа имеют постоянные метки, переходим к шагу
2.
Пятая итерация
ШАГ 2
. Находим Г(x
4
) = { x
3
, x
5
, x
6
, x
7
}. Метки вершин x
3
, x
5
и x
6
временные,
следовательно пересчитываем их значения:
L(x
3
) = min [ 23 , 7+25 ] = 23,
L(x
5
)= min[29 , 7+5 ]=12,
L(x
6
)= min[17 , 7+16]=17.
ШАГ 3
. На данном шаге итерации имеем следующие временные метки вершин:
L(x
3
)=23, L(x
5
)=29, L(x
6
)=17, L(x
9
)=11.
Очевидно, что минимальную метку, равную 11 имеет вершина x
9
.
ШАГ 4
. За следующую текущую метку принимаем вершину x
9
, т.е. p = x9, а ее
метка становится постоянной,
L(x
9
)=11
+
ШАГ 5
. Так как не все вершины графа имеют постоянные метки, переходим к шагу
2.
шестая итерация
ШАГ 2
. Находим Г(x
9
)={x
1
, x
2
, x
6
, x
7
, x
8
}. Метка вершины x
6
временная,
следовательно пересчитываем ее значение:
L(x
6
)= min[17 , 11+9]=17.
ШАГ 3
. На данном шаге итерации имеем следующие временные метки вершин:
L(x
3
)=23, L(x
5
)=12, L(x
6
)=17.
Очевидно, что минимальную метку, равную 12 имеет вершина x
5
.
ШАГ 4
. За следующую текущую метку принимаем вершину x
5
, т.е. p = x
5
, а ее
метка становится постоянной,
L(x
5
)=12
+
ШАГ 2. Находим Г(x8) = { x1, x5, x6, x9 }. Метки вершин x5, x6 и x9 временные,
следовательно пересчитываем их значения:
   L(x5) = min [ ∞ , 6+23 ] = 29,
   L(x6) = min [ 17 , 6+15 ] = 17,
   L(x9) = min [ 12 , 6+5 ] = 11.
ШАГ 3. На данном шаге итерации имеем следующие временные метки вершин:
L(x3) = 23,    L(x4) = 7,   L(x5) = 29, L(x6) = 17,   L(x9) = 11.
Очевидно, что минимальную метку, равную 7 имеет вершина x4.
ШАГ 4. За следующую текущую метку принимаем вершину x4, т.е. p = x4, а ее
метка становится постоянной, L(x4) = 7+
ШАГ 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу
      2.
Пятая итерация
ШАГ 2. Находим Г(x4) = { x3, x5, x6, x7 }. Метки вершин x3, x5 и x6 временные,
следовательно пересчитываем их значения:
      L(x3) = min [ 23 , 7+25 ] = 23,
      L(x5)= min[29 , 7+5 ]=12,
      L(x6)= min[17 , 7+16]=17.
ШАГ 3. На данном шаге итерации имеем следующие временные метки вершин:
L(x3)=23,             L(x5)=29,          L(x6)=17,          L(x9)=11.
Очевидно, что минимальную метку, равную 11 имеет вершина x9.
ШАГ 4. За следующую текущую метку принимаем вершину x9, т.е. p = x9, а ее
метка становится постоянной, L(x9)=11+
ШАГ 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу
      2.
      шестая итерация
ШАГ 2.        Находим Г(x9)={x1, x2, x6, x7, x8}.     Метка вершины x6 временная,
      следовательно пересчитываем ее значение:
      L(x6)= min[17 , 11+9]=17.
ШАГ 3. На данном шаге итерации имеем следующие временные метки вершин:
      L(x3)=23,             L(x5)=12,           L(x6)=17.
Очевидно, что минимальную метку, равную 12 имеет вершина x5.
ШАГ 4. За следующую текущую метку принимаем вершину x5, т.е. p = x5, а ее
      метка становится постоянной, L(x5)=12+

Страницы