Все алгоритмы для поиска кратчайших путей основаны на технике, называемой релаксацией.
Для каждой вершины vÎ V мы храним некоторое число d[v], являющееся верхней оценкой веса кратчайшего пути из s в v (далее будет использоваться термин – оценка кратчайшего пути).
Начальное значение оценки кратчайшего пути и массива p устанавливается процедурой
INITIALIZE-SINGLE-SOURCE (G,s)
1 for (для) всех вершины vÎ V[G]
2 do d[v]´
3 p [v] ¬ NIL
4 d[s]¬0
Релаксация ребра (u,v) Î E состоит в следующем: значение d [v] уменьшается до d [u] + w(u,v) ( если второе значение меньше первого). Одновременно с изменением d [v] меняется значение p [v].
RELAX (u,v,w)
1if d [v] > d [u] + w(u,v)
2 then d [v] ¬ d [u] + w(u,v)
3 p [v] ¬u
Пример релаксации
Доказательство правильности алгоритмов поиска кратчайших путей приводится в работе
Т.Кормен, Ч.Лейзерсон, Р.Ривест Алгоритмы: построение и анализ. М.:МЦНМО, 1999. – 960 с.