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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

ШАГ 4. За следующую текущую метку принимаем вершину x
7
, т.е. p = x
7
, а ее
метка становится постоянной,
L(x
7
) = 3
+
.
ШАГ 5
. Так как не все вершины графа имеют постоянные метки, переходим к шагу
2.
Вторая итерация
Граф с текущими значениями меток вершин показан на рис. 29.
ШАГ 2
. Находим Г(x
7
) = { x
2
, x
4
, x
6
, x
9
}. Метки всех вершин временные,
следовательно пересчитываем их значения:
L(x
2
)= min [10, 3+2 ] = 5,
L(x
4
)= min [ ∞, 3+4 ] = 7,
L(x
6
)= min [ ∞ , 3+14 ] = 17,
L(x
9
)= min [ 12, 3+24 ] = 12.
ШАГ 3
. На данном шаге итерации имеем следующие временные метки вершин:
L(x
2
) = 5, L(x
3
) = ∞,
L(x
4
) =7, L(x
5
) = ∞,
Рис. 29 Пометки в конце первой итерации
x
1
x
8
x
5
x
9
x
7
x
8
x
2
x
3
x
4
x
6
0
+
10
∞
∞
∞
∞
3
+
6
12 
ШАГ 4. За следующую текущую метку принимаем вершину x7, т.е. p = x7, а ее
метка становится постоянной, L(x7) = 3+ .
ШАГ 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу
2.

                                     10                     ∞
                           x2                         x3

                                                 +
                      0+                     x7 3
                                                                     ∞
                     x1
                                                                     x4

                                     x9 12           x6 ∞

                                                                 ∞
                                x8    6                     x5


                   Рис. 29 Пометки в конце первой итерации

      Вторая итерация
Граф с текущими значениями меток вершин показан на рис. 29.
ШАГ 2. Находим Г(x7) = { x2, x4, x6, x9}. Метки всех вершин временные,
следовательно пересчитываем их значения:
      L(x2)= min [10, 3+2 ] = 5,
      L(x4)= min [ ∞, 3+4 ] = 7,
      L(x6)= min [ ∞ , 3+14 ] = 17,
      L(x9)= min [ 12, 3+24 ] = 12.
ШАГ 3. На данном шаге итерации имеем следующие временные метки вершин:
      L(x2) = 5,    L(x3) = ∞,
      L(x4) =7,     L(x5) = ∞,

Страницы