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

UptoLike

ВУЗ: 

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

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

Рубрика: 

14
x
3
∞
2
2
∗
x
4
∞
1
∗
x
5
∞
6 5
4
∗
x
6
∞ ∞
2
2∗
x
7
∞
9 6
6
∗
x
8
∞ ∞ ∞ ∞
5
5
∗
∞ ∞ ∞ ∞ ∞ ∞
6
6
∗
Третья итерация.
Шаг 1. Г(x
2
) = x
1
, x
4
, x
5
. Вершины x
4
и x
5
имеют временные метки.
Обновляем метки.
L(x
4
) = min 6, 3+2 = 5,
L(x
5
) = min 2 , 5+2 = 2.
Шаг 2. min L(x
4
), L(x
5
), L(x
6
), L(x
7
), L(x
8
) = min 5,2, 9, ∞, ∞ =2.
Наименьшую метку имеет вершина x
5
. Эта метка становится постоянной, т.е.
L
∗
(x
5
) = 2.
Четвертая итерация.
Шаг 1. Г(x
5
) = x
2
, x
3
, x
4
, x
7
. Временные метки имеют вершины x
4
и
x
7
.
Обновляем их.
L(x
4
) = min 5, 2+2 = 4,
L(x
7
) = min ∞, 3+2 = 5.
Шаг 2. min L(x
4
), L(x
6
), L(x
7
), L(x
8
) = min 4, 9, 5, ∞ = 4.
Величина x
4
получает постоянную метку L
∗
(x
4
) = 4.
Пятая итерация.
Шаг 1. Г(x
4
) = x
1
, x
2
, x
5
, x
6
. Временную метку имеет только вершина x
6
.
Ее новая метка
L(x
6
) = min 9, 2+4 = 6,
Шаг 2. . min L(x
6
), L(x
7
), L(x
8
) = min 6, 5, ∞ = 5.
Полагаем L
∗
(x
7
) = 5.
Шестая итерация.
Шаг 1. Г(x
7
) = x
5
, x
6
, x
8
. Временные метки - у вершин x
6
и x
8
.
Имеем
L(x
6
) = min 6, 2+5 = 6,
L(x
8
) = min ∞, 1+5 = 6.
Шаг 2. min L(x
6
), L(x
8
) = min 6, 6 = 6.
Любую из меток L(x
6
), L(x
8
) можно сделать постоянной. Пусть L
∗
(x
6
) = 6.
Седьмая итерация.
Шаг 1. Г(x
6
) = x
1
, x
4
, x
7
, x
8
. Единственная вершина из Г(x
6
) с
временной меткой - это x
8
.
L(x
8
) = min 6, 2+6 = 6.
Шаг 2. min L(x
8
) = min 6 = 6. Вершина x
8
получает постоянную
метку L
∗
(x
8
) = 6.

Страницы