Основы дискретной математики. Щипцов В.В - 15 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

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

Рубрика: 

15
Процесс расстановки меток закончен. Значение постоянной метки
вершины x
8
дает кратчайшее расстояние между x
1
и x
8
, которое равно 6.
Для нахождения кратчайшего пути между x
1
и x
8
воспользуемся
соотношением
L
∗
(x
j
) = L
∗
(x
i
) + R
ij
, (2)
в котором вершина x
i
предшествует вершине x
j
. Полагаем в этом
соотношении j=8 и ищем значение i, т.е. вершину, предшествующую вершине
x
8
на кратчайшем пути. Имеем
6 = L
∗
(x
i
) + R
ij
, (3)
На графе (рис.3) вершина x
8
имеет только две смежные с ней вершины
x
6
и x
7
. Непосредственной проверкой убеждаемся, что только L
∗
(x
7
) = 5 и R
78
= 1 удовлетворяют соотношению (3), а данные, связанные с вершиной x
6
, ему
не удовлетворяют. Следовательно, на кратчайшем пути из x
1
в x
8
вершине x
8
предшествует вершина x
7
. Аналогичным образом находим, что вершине x
7
предшествует вершина x
5
, так как
5 = L
∗
(x
7
) = L
∗
(x
5
) + R
57
= 2+3.
Вершине x
5
предшествует вершина x
3
:
2 = L
∗
(x
5
) = L
∗
(x
3
) + R
35
= 1+1,
а вершине x
3
предшествует вершина x
1
. Таким образом, кратчайший путь из
x
1
в x
8
S= x
1
, x
3
, x
5
, x
7
, x
8
.
3) Построим дерево кратчайших путей для данного графа. Говоря
другими словами, следует найти связный подграф исходного графа, который не
содержал бы циклов и в котором длина пути от вершины x
1
(корня дерева) до
каждой из вершин графа была бы наименьшей по сравнению с любым другим
путем из x
1
до рассматриваемой вершины. Один такой путь из x
1
в x
8
уже
найден в предыдущем пункте. Очевидно, что каждый из путей из x
1
до любой
вершины построенного кратчайшего пути, также будет минимальным. Остается
найти кратчайшие пути из x
1
до вершин графа, не лежащих на S. Имеем 3
вершины x
2
, x
4
, x
6
, не лежащие на S. Очевидно, что кратчайший путь из x
1
в x
2
совпадает с ребром графа x
1
x
2
.
Найдем кратчайший путь из x
1
в x
6
. Запишем соотношение (2) для вершины
x
6
(j=6) и найдем вершину, предшествующую x
6
, т.е. вычислим значение x
i
.
В соответствии с таблицей 2
6 = L
∗
(x
6
) = L
∗
(x
i
) + R
i6
. (4)
Вершина x
6
имеет четыре смежных с ней вершины: x
1
, x
4
, x
7
, x
8
. Как
видно из таблиц 1,2, только данные вершины x
4
L
∗
(x
4
) = 4, R
46
=2
удовлетворяют соотношению (4), а данные вершин x
1
, x
7
, x
8
нет.
Следовательно, вершина x
4
является предшествующей для x
6
на кратчайшем
пути из x
1
в x
6
. Найдем далее вершину, которая предшествует вершине x
4
.
Для этого запишем соотношение (2) для j=4
4 = L
∗
(x
4
) = L
∗
(x
i
) + R
i4
.
Рассуждая аналогичным образом, находим, что из четырех вершин x
1
, x
2
,
x
5
, x
6
только данные вершины x
5
(L
∗
(x
5
) = 2, R
54
= 2) удовлетворяют
последнему соотношению. Следовательно, вершина x
5
предшествует вершине
x
4
. Оставшаяся часть кратчайшего пути из x
1
до x
5
, очевидно, совпадает с

Страницы