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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

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


                                                    +
                     0+                         x7 3
                                                                              7+
                     x1
                                                                              x4

                                     x9    11            x6 17

                                                                          ∞
                                x8    6+                         x5

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



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

Страницы