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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

x
1
=р,
ШАГ2.
Г(р)={x
2
, x
3
, x
4
},
L(x
2
)=min[∞, 0+5]=5,
L(x
3
)=min[∞, 0+14]=14,
L(x
4
)=min[∞, 0+10]=10.
ШАГ3.
L(x
2
)=5, L(x
5
)= ∞, L(x
8
)= ∞,
L(x
3
)=14, L(x
6
)= ∞, L(x
9
)= ∞,
L(x
4
)=10 , L(x
7
)= ∞, L(x
10
)= ∞.
ШАГ4.
L(x
2
)=5
+
.
ШАГ5.
P= x
2.
Вторая итерация.
ШАГ2.
Г(р)={x
1
, x
3
,x
6
},
L(x
3
)=min[14, 5+19]=14,
L(x
6
)=min[∞, 5+3]=8.
ШАГ3.
L(x
2
)=5
+
, L(x
5
)= ∞, L(x
8
)= ∞,
L(x
3
)=14, L(x
6
)=8, L(x
9
)= ∞,
L(x
4
)=10, L(x
7
)= ∞, L(x
10
)= ∞ .
ШАГ4.
L(x
6
)=8
+.
ШАГ5.
P= x
6.
Третья итерация.
ШАГ2.
Г(р)={x
2
, x
3
, x
7,
x
8
},
L(x
3
)=min[14, 8+5]=13,
L(x
7
)=min[∞, 8+9]=17,
L(x
8
)=min[∞, 8+8]=16.
ШАГ3.
L(x
2
)=5
+,
L(x
5
)= ∞, L(x
8
)=16,
L(x
3
)=13, L(x
6
)=8
+,
L(x
9
)= ∞,
L(x
4
)=10, L(x
7
)=17, L(x
10
)= ∞ .
ШАГ4.
L(x
4
)=10
+.
ШАГ5.
P= x
4.
Четвертая итерация.
ШАГ2.
Г(р)={. . . . . . . . . . . . },
L(x
3
)=min[. . . . . . . . . . . .]= . . . . .,
L(x
5
)=min. . . . . . . . . . . .]= . . . . . ,
ШАГ3. 
x1=р,
ШАГ2.
 Г(р)={x2, x3, x4},
L(x2)=min[∞, 0+5]=5,
L(x3)=min[∞, 0+14]=14,
L(x4)=min[∞, 0+10]=10.
ШАГ3.
L(x2)=5,         L(x5)= ∞,             L(x8)= ∞,
L(x3)=14,        L(x6)= ∞,             L(x9)= ∞,
L(x4)=10 ,       L(x7)= ∞,             L(x10)= ∞.
ШАГ4.
L(x2)=5+.

ШАГ5.
P= x2.

Вторая итерация.
ШАГ2.
Г(р)={x1, x3,x6},
L(x3)=min[14, 5+19]=14,
L(x6)=min[∞, 5+3]=8.
ШАГ3.
L(x2)=5+ ,      L(x5)= ∞,              L(x8)= ∞,
L(x3)=14,        L(x6)=8,              L(x9)= ∞,
L(x4)=10,        L(x7)= ∞,             L(x10)= ∞ .
ШАГ4.
L(x6)=8+.
ШАГ5.
P= x6.

Третья итерация.
ШАГ2.
Г(р)={x2, x3, x7, x8},
L(x3)=min[14, 8+5]=13,
L(x7)=min[∞, 8+9]=17,
L(x8)=min[∞, 8+8]=16.
ШАГ3.
L(x2)=5+,        L(x5)= ∞,             L(x8)=16,
L(x3)=13,         L(x6)=8+,            L(x9)= ∞,
L(x4)=10,         L(x7)=17,            L(x10)= ∞ .
ШАГ4.
L(x4)=10+.
ШАГ5.
P= x4.

Четвертая итерация.
ШАГ2.
Г(р)={. . . . . . . . . . . . },
L(x3)=min[. . . . . . . . . . . .]= . . . . .,
L(x5)=min. . . . . . . . . . . .]= . . . . . ,
ШАГ3.

Страницы