2014-02-09
488
Шаг 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. Пометки в начале второй итерации
