М.А. Басараб, А.Б. Домрачева, В.М. Купляков
6
просматриваются все ребра (
v
,
t
0
), исходящие из вершины
v
, и для
каждой вершины
t
0
алгоритм пытается улучшить значение
d
[
t
0
].
Пусть длина текущего ребра равна len, тогда шаги алгоритма (релак-
сации) выглядят так:
d
[
t
0
] = min(
d
[
t
0
],
d
[
v
] + len).
На этом текущая итерация заканчивается, алгоритм переходит к
следующей итерации (снова выбирается вершина с наименьшей
длиной
d
[
v
], из нее производятся релаксации и т. д.). При этом по-
сле
n
итераций все вершины графа станут помеченными и алгоритм
свою работу завершает. Утверждается, что найденные значения
d
[
v
]
и есть искомые длины кратчайших путей из
s
в
v
.
Следует отметить, что если не все вершины графа достижимы из
вершины
s
, то значения
d
[
v
] для них так и останутся бесконечными.
Понятно, что несколько последних итераций алгоритма будут как раз
выбирать эти вершины, но никакой полезной работы производить не
будут (поскольку бесконечное расстояние не сможет прорелаксиро-
вать другие, пусть и бесконечные расстояния). Поэтому алгоритм
можно останавливать, как только будет выбрана вершина с беско-
нечным расстоянием.
Обычно нужно знать не только длины кратчайших путей, но и
получить сами пути. Покажем, как сохранить информацию, доста-
точную для последующего восстановления кратчайшего пути из
s
до любой вершины. Для этого достаточно так называемого массива
«предков»: массива
p
[ ], в котором для каждой вершины
v
≠
s
хра-
нится номер вершины
p
[
v
], являющейся предпоследней в кратчай-
шем пути до вершины
v
. Здесь используется тот факт, что если мы
возьмем кратчайший путь до какой-то вершины
v
, а затем удалим
из этого пути последнюю вершину, то получится путь, оканчива-
ющийся некоторой вершиной
p
[
v
], и этот путь будет кратчайшим
для вершины
p
[
v
]. Если имеется массив «предков», то кратчайший
путь можно будет восстановить по нему, просто каждый раз беря
«предка» от текущей вершины, пока мы не придем в стартовую
вершину
s —
так получится искомый кратчайший путь, но запи-
санный в обратном порядке. Итак, кратчайший путь
P
до вершины
v
равен:
P
= (
s
, …,
p
[
p
[
p
[
v
]]],
p
[
p
[
v
]],
p
[
v
],
v
).
Массив «предков» строится просто: при каждой успешной релак-
сации, т. е. когда из выбранной вершины
v
происходит улучшение
расстояния до некоторой вершины
t
0
, записываем, что «предком»
вершины
t
0
является вершина
v
:
p
[
t
0
] =
v
.
Алгоритм Дейкстры учитывает веса при продвижении по графу, к
тому же он обновляет данные в ранее достигнутых узлах пути. Таким
образом, гарантированно будет найден кратчайший путь, если он су-
