Дискретная математика. Громов Ю.Ю - 83 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

83
Для нашего графа на втором шаге получим:
L(v
10
) = min {l (v
10
, v
13
) + L(v
13
)} = min {5 + 2} = min {7} = 7
⇒
D(v
10
) =
= (v
10
, v
13
);
L(v
11
) = min {l (v
11
, v
13
) + L(v
13
), l (v
11
, v
14
) + L(v
14
)} = min {2 + 2, 8 + 1} =
= min {4, 9} = 4
⇒
D(v
11
) = (v
11
, v
13
);
L(v
12
) = min {l (v
12
, v
14
) + L(v
14
)} = min {4 + 1} = min {5} = 5
⇒
D(v
12
) =
= (v
12
, v
14
).
Продолжив определение кратчайших расстояний L(
1+j
x
v
) и выбор
соответствующих им дуг D(
1+j
x
v
) для j = 2, 3, 4 и 5, в результате получим
дерево кратчайших расстояний, представленное утолщёнными рёбрами
на рис. 47.
Задачи и упражнения
1. Определите по алгоритму, основанному на итерационном уточ-
нении дерева расстояний, длины кратчайших путей от вершины v
0
до ка-
ждой вершины графа G:
2. Определите по алгоритму, основанному на методе динамическо-
го программирования, длины кратчайших путей от каждой вершины до
вершины v
15
графа G:
Рис. 47
ν
6
ν
3
ν
1
ν
0
ν
10
ν
7
ν
4
ν
2
ν
13
ν
11
ν
8
ν
5
ν
k
ν
14
ν
12
ν
9
1
5
7
2
1
3
5
2
2
2
4
1
0
4
1
3
3
2
4
5
4
2
8
2
L(v
13
) = 2
L(v
14
) = 1
L(v
10
) = 7
L(v
12
) = 5
4
10
8
6
7
9
8
11
12
10
10
ν
0
ν
1
ν
2
ν
3
ν
4
ν
5
ν
6
ν
7
ν
8
ν
9
ν
10
ν
11
5
2
3
2
3
1
1
3
1
4
3
4
1
1
1
3
2
ν
12
ν
13
ν
14
ν
15
1
1 5
1
1
4
5

Страницы