Составители:
Рубрика:
103
()()()
1,4 4,2 1,5 5,2 1,6 6,2
;;]ddd
γ+ γ+ γ+ =
()()()( )()()
1
min[ 30 ; 30 0 ; 15 ; 20 15 ; 25 ; 40 30
=∞+ +∞+ +∞+∞+=
.
Так как минимальное значение в выражении находится на втором
месте, что соответствует вершине B, то в минимальном пути от верши-
ны A к вершине B нет промежуточных вершин. Таким образом, этот
путь будет A → B.
Элемент δ
2
1,2
матрицы Δ
2
, соответствующий второму по протяжен-
ности пути от вершины A к вершине B:
[]
2
1,2
2
min ... 35.δ= =
Так как второе по минимуму выражение находится на четвертом
месте, что соответствует вершине D, то второй по протяженности путь
от вершины A к вершине B проходит через вершину D.
Рассмотрим для примера нахождение кратчайшего пути от верши-
ны A к вершине C. Тогда
()( )( )
1
1,3 1,1 1,3 1,2 2,3 1,3 3,3
1
min[ ; ; ;ddd
δ= γ+ γ+ γ+
()()()
1,4 4,3 1,5 5,3 1,6 6,3
;;]ddd
γ+ γ+ γ+ =
()()()( )()()
min[ 40 ; 30 15 ; 0 ; 20 22 ; 25 ; 45 40.
=∞+ +∞+ +∞+∞+=
Так как минимум находится на 4-м месте, кратчайший путь от A к C
проходит через вершину D. Чтобы найти кратчайший путь от вершины
D к вершине C необходимо вычислить
()( )( )
1
4,3 4,11,34,22,34,33,3
1
min[ ; ; ;ddd
δ= γ+ γ+ γ+
()()()
4,4 4,3 4,5 5,3 4,6 6,3
;;]ddd
γ+ γ+ γ+ =
()()()()()()
min[ 20 40 ; 15 15 ; 20 0 ; 20 ; 25 ; 40 45 20.
=+++∞+∞++=
Так как минимум находится на 3-м месте, то между вершинами D и
C нет промежуточных вершин. Таким образом кратчайший путь от вер-
шины A к вершине C будет A → D → C.
Страницы
- « первая
- ‹ предыдущая
- …
- 101
- 102
- 103
- 104
- 105
- …
- следующая ›
- последняя »
