Составители:
Рубрика:
100
Поэтому если выполняется условие (5.7), то кратчайший путь от УК
i
проходит по ветви β
i,j
. Переходя к УК
j
, находим следующую ветвь, для
которой выполняется последнее условие и которая также входит в этот
кратчайший путь. Так, шаг за шагом можно определить все ветви, об-
разующие кратчайший путь.
Исключив затем кратчайший путь из рассмотрения, подобным об-
разом определяются и другие пути от исходящего УК
i
к входящему
УК
j
Данный метод выбора кратчайших путей от одного узла до всех
остальных узлов называется методом Флойда.
При матричном методе определения кратчайшего пути дополнительно
к дистанционной матрице на основе матрицы длин непосредственных
связей составляется так называемая модернизированная матрица длин
непосредственных связей Г, элементы главной диагонали которой в от-
личие от элементов l
i,j
= 0 имеют значения l
i,j
= ∞, где значком ∞ обо-
значена бесконечность. Таким образом, матрица Г легко может быть
получена по матрице L
1
.
Для рассматриваемого случая
ABCDE F
A3020
B1515
C152025
Г.
D201520 25
E251040
F15 2540
∞∞∞∞
∞∞ ∞∞
∞∞ ∞
=
∞∞
∞∞ ∞
∞∞ ∞
Замена элемента
1
,ii
l
на
1
,ii
l =∞
в матрице Г означает, что длина пути
в УК
i
принимается бесконечно большой. Это дает возможность не рас-
сматривать все пути проходящие через исходный узел, т. е. позволяет
исключить путь (β
i,i
, β
i, j
), изображенный на рис. 5.3, б. Полученная та-
ким способом модернизированная матрица длин Г = ||γ
i.j
|| умножается
на дистанционную матрицу D с использованием тех же операций, что и
ранее. При умножении матрицы Г на матрицу D образуется матрица
Δ = ГD, элементы которой используются для получения дисперсионных
Страницы
- « первая
- ‹ предыдущая
- …
- 98
- 99
- 100
- 101
- 102
- …
- следующая ›
- последняя »
