Ш А Г 3. Среди всех вершин с временными пометками найти такую, для которой
L(x*i)=min[L(xi)].
Ш А Г 4. Считать пометку вершины x*i постоянной и положить p=x*i .
Ш А Г 5(a ). {При нахождении пути отs к t}
Если текущая вершина p является искомой, т. е. p = t, то L(p) является длиной кратчайшего пути от s к t. Останов. Если p t, перейти к шагу 2. Ш А Г 5(б). {При нахождении путей отsко всем вершинам}
Если все вершины отмечены постоянными метками, то эти метки дают длины кратчайших путей. Если некоторые метки являются временными, то следует перейти к шагу 2. Как только длины кратчайших путей от вершины s будут найдены, сами пути можно получить с помощью рекурсивной процедуры (*). Так как вершина x*i непосредственно предшествует вершине хi в кратчайшем пути от s к хi , то для любой вершины хi соответствующую вершину x*i можно найти как одну из оставшихся вершин, для которой
L(x*i)+c( x*i, xi)=L( xi).(*)
Если кратчайший путь от s до любой вершины хi является единственным, то дуги (x*i, xi) этого кратчайшего пути образуют ориентированное дерево с корнем s. Если существует несколько кратчайших путей от s к какой-либо другой вершине, то при некоторой фиксированной вершине x*i соотношение (*) будет выполняться для более чем одной вершины хi . В этом случае выбор может быть либо произвольным (если нужен какой-то один кратчайший путь между s и хi ), либо таким, что рассматриваются все дуги (x*2,x2), входящие в какой-либо из кратчайших путей, и при этом совокупность всех таких дуг образует не ориентированное дерево, а общий граф, называемый базой относительно s.
П р и м е р. Рассмотрим граф смешанного типа, изображенный на рис. 9.2,а, где каждое неориентированное ребро рассматривается как пара противоположно направленных дуг равного веса. Матрица весов приведена на рис. 9.2,б. Требуется найти все кратчайшие пути от вершины х1 ко всем остальным вершинам.
Рис. 9.2. Пример поиска кратчайшего пути: а – граф; б – матрица весов дуг
Постоянные пометки будем помечать знаком +.
Ш А Г 1. Присвоим L(х1) = 0, L(хi) = ∞ для всех хi , кроме х1 . Положим р = х1 .