Графы и сети. Харитонова Е.В. - 75 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

74
Рис. 3.21
РЕШЕНИЕ. Минимальная длина труб: 5 + 6 + 4 + 3 + 7 + 5 + 6 + 5 = 41 (рис. 3.21).
Нахождение кратчайшего пути
Задача состоит в нахождении связанных между собой дорог на транс-
портной сети, которые в совокупности имеют минимальную длину от исходно-
го пункта до пункта назначения.
Введем обозначения:
dij – расстояние на сети между смежными узлами i и j;
U
j
– кратчайшее расстояние между узлами i и j, U
1
= 0.
Формула для вычисления
U
j
:
Из формулы следует, что кратчайшее расстояние U
j
до узла j можно вы-
числить лишь после того, как определено кратчайшее расстояние до каждого
предыдущего узла
i, соединенного дугой с узлом j. Процедура завершается, ко-
гда получено
U
i
последнего звена.
Определить кратчайшее расстояние между узлами 1 и 7 (рис. 3.22).
РЕШЕНИЕ. Найдем минимальные расстояния:
U
1
= 0,
U
2
= U
1
+ d
12
= 0 + 2 = 2,
U
3
= U
1
+ d
13
= 0 + 4 = 4,
U
4
= min{ U
1
+ d
14
; U
2
+ d
24
; U
3
+ d
34
} = min{0 + 10; 2 + 11; 4 + 3} = 7,
U
5
= min{U
2
+ d
25
; U
4
+ d
45
} = min{2 + 5; 7 + 8} = 7,
U
6
= min{ U
3
+ d
36
; U
4
+ d
46
} = min{4 + 1; 7 + 7} = 5,
U
7
= min{ U
5
+ d
57
; U
6
+ d
67
} = min{7 + 6; 5 + 9} = 13.
1
2
5
9
8
7
3
4
6
5
6
7
4
6
5
5
3
Приемный пункт
min
i
=
j
U
=
{
}
iji
i
dU +min
Кратчайшее расстояние до предыду-
щего узла i плюс расстояние
между текущим узлом j и предыду-
щим узлом i

Страницы