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

UptoLike

ВУЗ: 

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

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

Рубрика: 

13
Вершина x
3
, как имеющая минимальную временную метку, получает
постоянную метку L
∗
(x
3
) = 1.
Результаты вычислений будем оформлять в виде таблицы 2.
Таблица 2
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
1
2 1 6 9
x
2
2 3 5
x
3
1 1
x
4
6 3 2 2
x
5
5 1 2 3
x
6
9 2 2 2
x
7
3 2 1
x
8
2 1
Рис.3
Вторая итерация.
Шаг 1. Рассматриваем Г(x
3
) = x
1
, x
5
.
Временную метку имеет только вершина x
5
. Обновляем ее ( метку ).
L (x
5
) = min ∞, 1+1 = 2
Шаг 2. Вычисляем min по всем временным меткам.
min L(x
2
), L(x
4
), L(x
5
), L(x
6
), L(x
7
), L(x
8
) = min 2, 6,2, 9, ∞, ∞ =2.
В качестве постоянной можно взять любую из меток L(x
2
) и L(x
5
), которые
совпадают и равны вычисленному минимуму.
Пусть постоянную метку получит, например, вершина x
2
, т.е. L
∗
(x
2
)=2.
Таблица 3
вершины
И т е р а ц и и
x
1
0 1 2 3 4 5 6 7
x
2
0
∗

Страницы