Ш А Г 2. Находим Г(х6) = { х3, х5, х7, х8, х9 }. Метка вершины х3 временная, следовательно, пересчитываем ее значение:
L(х3) = min [ 23, 17 + 20 ] = 23.
Ш А Г 3. На данном шаге итерации имеем одну временную метку вершины: L(х3) = 23, которая становится постоянной.
Ш А Г 4. Все вершины имеют постоянные метки, поэтому алгоритм окончен.
Для нахождения кратчайшего пути между вершинами, например, х2 и начальной х1 последовательно используем соотношение (**): L(x'2)+c(x'2,x2)=L(x2)=5, где вершина x'2 – это вершина, непосредственно предшествующая х2 в кратчайшем пути от х1 к х2 .
Единственной такой вершиной является вершина х7 . Далее соотношение (**) применяем второй раз:
L(x7')+ с(x7’, x7) = L(x7) = 3
Единственной такой вершиной является вершина х1 . Поэтому кратчайший путь от х1 к х2 есть (х1, х7, х2). Вершина х1 , называемая базой и дающая все кратчайшие пути от х1 представляет дерево.
Рис. 9.5.