Составители:
Рубрика:
95
Если длина пути μ
i1, j
равна L
i1, j
, то
L
i,j
= L
i,i1
+ L
i1, j
.
Так как μ
i, j
является кратчайшим, то
,,,
1,
min ( ),
ivvi
vi iN
LlL
εε
=
=+
5.1)
где N – число узлов сети.
Для нахождения кратчайшего пути от узла ε к узлу j необходимо
просмотреть все возможные пути и выбрать тот, у которого длина наи-
меньшая.
Имеется ряд методов определения длины кратчайшего пути. Их
можно разделить на две группы:
методы нумерации узлов;
матричные методы.
Матричный метод определения кратчайших путей позволяет найти
длины кратчайших путей между всеми узлами сети одновременно и
основывается на применении операций над матрицами расстояний.
Структуру сети связи с указанием длин ветвей можно описать в
виде матрицы расстояний (длин) непосредственных связей
1
.
ij
Ll=
Элемент
1
ij
l
определяет длину ветви β
i,j
.
Рассмотрим пример. Пусть сеть связи имеет вид, изображенный на
рис. 5.2.
Рис. 5.2. Пример коммуникационной сети связи
A
B
C
F
E
D
30 15
15
15
15
25 25
20
20
20
20
10
40
Страницы
- « первая
- ‹ предыдущая
- …
- 93
- 94
- 95
- 96
- 97
- …
- следующая ›
- последняя »
