Шаг 2. G(p) = G(x1) = {х2, х7, х8, х9}. Все эти вершины имеют временные пометки.
Рис.3.34. Пример графа к алгоритму Дейкстры
| Таблица 3.4. Матрица смежности с весами для графа
|
| | х1
| х2
| х3
| х4
| x5
| x6
| x7
| x8
| x9
|
| х1
|
|
|
|
|
|
|
|
|
|
| х2
|
|
|
|
|
|
|
|
|
|
| х3
|
|
|
|
|
|
|
|
|
|
| х4
|
|
|
|
|
|
|
|
|
|
| x5
|
|
|
|
|
|
|
|
|
|
| x6
|
|
|
|
|
|
|
|
|
|
| x7
|
|
|
|
|
|
|
|
|
|
| x8
|
|
|
|
|
|
|
|
|
|
| x9
|
|
|
|
|
|
|
|
|
|
В соответствии с формулой (8) уточняем пометки:
l(х2) = min(¥, 0+ + 10) = 10; l(х7) = 3; l(х8) = 6; l(x9) = 12.
Шаг 3. min(10, 3, 6, 12, ¥ ) = 3
х2 х7 х8 х9 х3, х4, х5, х6
Вершина х7 получает постоянную пометку: 1(х7) = З+ .
Далее р = x7.
Шаг 4. Так как не все вершины имеют постоянные пометки, то переходим к шагу 2. На рис. 3.35 приведены значения пометок вершин графа. Здесь выделены вершины с постоянными пометками.
Рис. 3.35. Пометки в начале второй итерации
