Составители:
Рубрика:
97
Произведения
11 1 1
,, , ,
и
ii ij ij jj
ll l l××
фактически соответствуют одно-
транзитным путям, так как длина пути (задержка) внутри УК (т. е.
11
,,
и
ii j j
ll
) не принимается во внимание.
Для подсчета длины каждого из таких n транзитных путей необходи-
мо операцию умножения заменить операцией сложения, т. е. вместо
11
,,ik k j
ll×
будем иметь
11
,,
.
ik k j
ll+
При наличии нескольких параллельных одно-двухтранзитных путей
(см. рис. 5.3, б) для определения длины кратчайшего пути между узла-
ми следует операцию сложения заменить операцией выбора из всех длин
минимальной длины одно- двухтранзитного пути, т. е. вместо (5.3) бу-
дем иметь
() ()( )
211111111
,,,,11,,22,,,
1,...,
min min ( ); ;... .
ij ik kj i j i j iN Nj
kN
lllllllll
=
=+=++ +
Таким образом, элемент
2
,ij
l
матрицы L
2
равен длине кратчайшего
пути от УК
i
к УК
j
среди всех одно- двухтранзитных путей.
При возведении матрицы L
1
в r-ю степень при использовании этих
операций получим матрицу
L
r
= L
r–1
× L
1
,
элемент которой
i
j
k
j
1
,
ij
l
1
,
kj
l
а) б)
i
j
k
i
1
,ii
l
1
,
ij
l
1
,ik
l
1
,ij
l
1
,
jj
l
1
,
kj
l
Рис. 5.3. Двухтранзитные пути
Страницы
- « первая
- ‹ предыдущая
- …
- 95
- 96
- 97
- 98
- 99
- …
- следующая ›
- последняя »
