Методы маршрутизации в вычислительных сетях. Крылов Ю.Д. - 11 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

11
Тогда матрицы L
1
и Г будут
1
030 20
01515
15 0 20 25
,
20 15 20 0 40
25 15 0 40
15 25 40 0
A
BC DE F
A
B
C
D
E
F
111
111
11
2
1
11
11
L
30 20
15 15
15 20 25
.
20 15 20 40
25 15 40
15 25 40
A
BC DE F
A
B
C
D
E
F
1111
11 11
11 1
2
11
11 1
11 1
Г
Тогда, например, элемент
1
1,2
1 ,определяющий минимальный по
протяженности путь от вершины A к вершине B матрицы D
1
, согласно
(8) будет
1
1,2
1 =
1
min
[(g
1,1
+ d
1,2
);(g
1,2
+ d
2,2
);(g
1,3
+ d
3,2
); (g
1,4
+ d
4,2
);
(g
1,5
+ d
5,2
); (g
1,6
+ d
6,2
)] =
=
1
min
[(¥ + 30); (30 + 0); (¥ + 15); (20 +15); (¥ + 25); (¥ + 40) = 30.
Так как минимальное значение в выражении находится на втором
месте, что соответствует вершине B, то в минимальном пути от верши-
ны A к вершине B нет промежуточных вершин.
Элемент
2
1,2
1 матрицы D
2
,
соответствующий второму по протяжен-
ности пути от вершины A к вершине B, будет:
2
1,2
1
=
2
min
[…. ] = 35.
Так как второе по минимуму выражение находится на четвертом
месте, что соответствует вершине D, то второй по протяженности путь
от вершины A к вершине B проходит через вершину D.
Выбрав кратчайшие пути от какого-либо узла ко всем остальным,
можно построить так называемое дерево крат-
чайших путей, в котором из всего множества
путей от узла указаны только кратчайшие от
него пути ко всем остальным узлам.
Например, для графа, представленного на
рис. 2, которому сопоставлена матрица L
1
не-
посредственных связей, дерево кратчайших
путей от вершины А изображено на рис. 4.
Дерево кратчайших путей является подде-
ревом дерева путей.
B
A
F
C
E
D
Рис. 4

Страницы