Вычислительные сети. Крылов Ю.Д. - 99 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

99
Аналогично
3
ABCDE F
A 0 30 40 20 65 45
B 35 0 15 15 40 40
C 40 15 0 20 25 45
.
D 20 15 20 0 45 25
E30252510035
F15404525400
L
=
Затем
4
ABCDEF
A 0 30 40 20 65 45
B 35 0 15 15 40 40
C 40 15 0 20 25 45
.
D 20 15 20 0 45 25
E30252510035
F15404525400
L
=
Здесь L
4
= L
3
, следовательно D = L
3
.
Рассмотренные методы позволяют определить длину кратчайшего
пути, но не указывают те ветви, которые входят в этот путь.
Определение самого кратчайшего пути связано с некоторой допол-
нительной процедурой.
Если для определения длины кратчайшего пути применяется способ
нумерации узлов, то при выполнении дополнительной процедуры учиты-
вается свойство веса УК
i
. Это свойство заключается в том, что суще-
ствует УК
j,
для которого выполняется равенство
W
i
= l
i,j
+ W
j
. (5.6)
Отсюда следует, что
W
i
– W
j
= l
i,j
. (5.7)

Страницы