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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

ШАГ 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу
2.
Седьмая итерация
ШАГ 2
. Находим Г(x
5
) = { x
4
, x
6
}. Метка вершины x
6
временная, следовательно
пересчитываем ее значение:
L(x
6
)= min [17 , 12+10 ] = 17.
ШАГ 3
. На данном шаге итерации имеем следующие временные метки :
L(x
3
)=23, L(x
6
)=17.
Очевидно, что минимальную метку, равную 17 имеет вершина x
6
.
ШАГ 4
. За следующую текущую метку принимаем вершину x
6
, т.е. p = x
6
, а ее
метка становится постоянной,
L(x
6
)=17
+.
ШАГ 5
. Так как не все вершины графа имеют постоянные метки, переходим к шагу
2.
Восьмая итерация
ШАГ 2
. Находим Г(x
6
) = { x
3
, x
5
, x
7
, x
8
, x
9
}. Метка вершины x
3
временная,
следовательно пересчитываем ее значение:
L(x
3
) = min [ 23 , 17+20 ] = 23.
ШАГ 3
. На данном шаге итерации имеем одну временную метку вершины:
L(x
3
)=23, которая становится постоянной.
ШАГ 4
. Все вершины имеют постоянные метки, поэтому алгоритм окончен.
Рис. 31 Окончательные пометки и х
1
- база.
x
1
x
8
x
5
x
9
x
7
x
8
x
2
x
3
x
4
x
6
0
+
5
+
23
+
7
+
12
+
17
+
3
+
6
+
11
+
ШАГ 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу
     2.
     Седьмая итерация
ШАГ 2. Находим Г(x5) = { x4, x6 }. Метка вершины x6 временная, следовательно
     пересчитываем ее значение:
     L(x6)= min [17 , 12+10 ] = 17.
ШАГ 3. На данном шаге итерации имеем следующие временные метки :
     L(x3)=23,        L(x6)=17.
Очевидно, что минимальную метку, равную 17 имеет вершина x6.
ШАГ 4. За следующую текущую метку принимаем вершину x6, т.е. p = x6, а ее
     метка становится постоянной, L(x6)=17+.
ШАГ 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу
     2.
     Восьмая итерация
ШАГ 2.    Находим Г(x6) = { x3, x5, x7, x8, x9 }.               Метка вершины x3 временная,
     следовательно              пересчитываем        ее     значение:
     L(x3) = min [ 23 , 17+20 ] = 23.
ШАГ 3. На данном шаге итерации имеем одну временную метку вершины:
     L(x3)=23, которая становится постоянной.
ШАГ 4. Все вершины имеют постоянные метки, поэтому алгоритм окончен.

                           5+                         23+
                 x2                            x3


                                        +
           0+                       x7 3
                                                                7+
           x1
                                                                x4
                                +                +
                           x9 11            x6 17

                                                          12+
                                +
                      x8    6                        x5




                           Рис. 31 Окончательные пометки и х1 - база.

Страницы