Составители:
Рубрика:
7
Произведения
11
,,ii ij
ll1 и
11
,,ij jj
ll1 фактически соответствуют однотран-
зитным путям, так как длина пути (задержка) внутри УК (т. е.
1
,ii
l и
1
,jj
l ) не принимается во внимание.
Для подсчета длины каждого из таких n транзитных путей необхо-
димо операцию умножения заменить операцией сложения, т. е. вмес-
то
11
,,ik kj
ll1 будем иметь
1
,ik
l +
1
,kj
l .
При наличии нескольких параллельных одно- двухтранзитных
путей (рису. 3,б) для определения длины кратчайшего пути между уз-
лами следует операцию сложения заменить операцией выбора из всех
длин минимальной длины одно- двухтранзитного пути, т. е. вместо
(3) будем иметь:
1
2
1
2
1
2
1
2
211111111
,,,,11,,22,,,
1,...,
min ; ; ... .
min
ij ik kj i j i j iN Nj
kN
lllllllll34344 4
Таким образом , элемент
2
,ij
l матрицы L
2
равен длине кратчайшего
пути от УК
i
к УК
j
среди всех одно- двухтранзитных путей.
При возведении матрицы L
1
в r-ю степень при использовании этих
операций получим матрицу
L
r
= L
r–1
*L
1
,
элемент которой
1212121 2
11 11 11 11
,,,,11,,22,,,
1,...,
min ; ; ...
min
rr rr r
ij ik kj i j i j iN Nj
kN
lllllllll34344 4
будет равен длине кратчайшего пути от УК
i
к УК
j
среди всех одно-
двух- и т. д. r-транзитных путей.
При наличии на сети N узлов коммутации число транзитных вет-
вей в пути без петель не может быть больше N–1 . Следовательно,
может потребоваться вычисление матрицы L
r
, у которой r £ N–1.
Для конкретной сети может оказаться, что при r < N–1
L
r
= L
r–1
. (4)
Так как при равенстве (4) всегда выполняется равенство
L
r+1
= L
r
,
вычисление матрицы более высокой степени прекращается, если в про-
цессе вычисления матриц встретится равенство (4).
Матрица L
r–1
при выполнении условия (4) называется дистанци
онной матрицей и обозначается
D = L
r–1
= L
r
= || d
i,j
|| . (5)
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
