Шаг пятый

а) Если надо найти путь от S к t:

- если p = t, то 1(р) является длиной кратчайшего пути, конец задачи;

- если р ≠ t, то перейти ко второму шагу.

б) Если требуется найти путь от S ко всем остальным вершинам:

- если все вершины отмечены как постоянные, то пометки этих вершин дают длины кратчайших путей, конец задачи;

- если некоторые пометки являются временными, перейти ко второму шагу.

-

Длина кратчайшего пути от исходной вершины S к любой вершине графа t равна величине постоянной пометки этой вершины t, т.е. l(S,t)=l(t ).

Для нахождения самого пути воспользуемся соотношением:

l(X_i*)+c(X_i*,X_i)=l(X_i), (2)

где X_i* - вершина, непосредственно предшествующая вершине X_i в кратчайшем пути от S к t

Если условие (2) выполняется, то дуга (X_i*,X_i) входит в кратчайший путь.

Используя изложенный выше алгоритм, определим кратчайший путь в графе G от заданной вершины Х₅ ко всем вершинам.

Шаг1 Присвоим начальные пометки вершинам:

l(X₅) = 0⁺;

X_i ≠ X₅, l(X_i) = ∞;

p = X₅,