Вычислительные сети. Крылов Ю.Д. - 104 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

104
Поступая аналогичным образом, можно составить матрицу кратчай-
ших путей между всеми вершинами, где в качестве элементов находят-
ся не расстояния, а идентификаторы промежуточных или конечных вер-
шин. Для рассматриваемого примера такая матрица будет иметь
следующий вид:
ABCDEF
A–BDDDD
BD–CDCD
CDB–DEE
.
DABC–CF
EDDCD–F
FADDDE–
Выбрав кратчайшие пути от какого-либо узла ко всем остальным,
можно построить так называемое дерево кратчайших путей, в котором
из всего множества путей от узла указаны только кратчайшие от него
пути ко всем остальным узлам.
Например, для графа (см. рис. 5.2), которому сопоставлена матри-
ца L
1
непосредственных связей,
дерево кратчайших путей изобра-
жено на рис. 5.4.
Дерево кратчайших путей являет-
ся поддеревом дерева путей (рис. 5.5).
Дерево кратчайших путей и де-
рево путей от узла ко всем осталь-
ным узлам для неориентированных
графов (сетей) совпадает с деревом
кратчайших путей и деревом путей
соответственно от всех узлов к рас-
сматриваемому узлу i. Для ориен-
тированных графов (сетей связи)
такого совпадения может и не
быть.
Рис. 5.4. Дерево кратчайших путей
от вершины А ко всем остальным
вершинам
B
D
C
F
A
E

Страницы