Составители:
Рубрика:
5
где N – число узлов сети.
Для нахождения кратчайшего пути от узла e к узлу j необходимо
просмотреть все возможные пути и выбрать тот, у которого длина наи-
меньшая.
Имеется ряд методов определения длины кратчайшего пути. Их
можно разделить на две группы: методы нумерации узлов и матрич-
ные методы.
Матричный метод определения кратчайших путей позволяет най-
ти длины кратчайших путей между всеми узлами сети одновременно и
основывается на применении операций над матрицами расстояний.
Структуру сети связи с указанием длин ветвей можно описать в
виде матрицы расстояний (длин) непосредственных связей:
L
1
= ||
1
,ij
l ||,
где элемент
1
,ij
l определяет длину ветви b
i,j
.
Пример.
Пусть сеть связи имеет вид, представленный на рис. 2.
15
25
40
A
B
F
E
D
25
10
15
30
20
20
20
20
C
15
15
Рис. 2
Цифры на ребрах и дугах соответствуют длинам ветвей. Тогда мат-
рица расстояний будет:
1
030 20
01515
15 0 20 25
.
20 15 20 0 25
25 10 0 40
15 25 40 0
A
BC DE F
A
B
C
D
E
F
111
111
11
2
1
11
11
L
(2)
Страницы
- « первая
- ‹ предыдущая
- …
- 3
- 4
- 5
- 6
- 7
- …
- следующая ›
- последняя »
