Составители:
Рубрика:
9
Здесь L
4
= L
3
, следовательно, D = L
3
.
Рассмотренные методы позволяют определить длину кратчайшего
пути, но не указывают те ветви, которые входят в этот путь.
Определение самого кратчайшего пути связано с некоторой допол-
нительной процедурой.
Если для определения длины кратчайшего пути применяется спо-
соб нумерации узлов, то при выполнении дополнительной процедуры
учитывается свойство веса УК
i
. Это свойство заключается в том, что
существует УК
j ,
для которого выполняется равенство:
W
i
= l
i,j
+W
j
. (6)
Отсюда следует, что
W
i
– W
j
= l
i,j
. (7)
Поэтому, если выполняется условие (7), то кратчайший путь от
УК
i
проходит по ветви b
i,j
. Переходя к УК
j
, находим следующую ветвь,
для которой выполняется последнее условие и которая также входит
в этот кратчайший путь. Так, шаг за шагом можно определить все
ветви, образующие кратчайший путь.
Исключив затем кратчайший путь из рассмотрения, подобным об-
разом определяются и другие пути от исходящего УК
i
к входящему
УК
j
. Данный метод выбора кратчайших путей от одного узла до всех
остальных узлов называется методом Флойда.
При матричном методе определения кратчайшего пути дополни-
тельно к дистанционной матрице на основе матрицы длин непосред-
ственных связей составляется так называемая матрица длин непос-
редственных связей Г, элементы главной диагонали которой в отли-
чие от элементов l
i,j
= 0 имеют значения l
i,j
= ¥, где значком ¥ обозначе-
на бесконечность.
Таким образом, матрица Г легко может быть получена по матрице L
1
.
Пример.
Для рассматриваемого случая
30 20
15 15
15 20 25
.
20 15 20 25
25 10 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
Г
Страницы
- « первая
- ‹ предыдущая
- …
- 7
- 8
- 9
- 10
- 11
- …
- следующая ›
- последняя »
