Поиск кратчайшего пути в графе

Поиск кратчайшего пути в графе между двумя точками - это нахождение такой последовательности дуг (или дуги), ведущей от начальной точки до конечной, при которой сумма их весов будет минимальной.

Рассмотрим задачу поиска кратчайшего пути между двумя заданными вершинами S и t для случая неотрицательной матрицы весов.

Наиболее эффективный алгоритм решения такой задачи создал Дейкстра. Этот метод основан на приписывании вершинам временных пометок, причем, пометка вершины дает верхнюю границу длины пути от S к этой вершине. Эти пометки (их величины) постепенно уменьшаются с помощью итерации, и на каждом шаге итерации только одна извременных пометок становится постоянной. Это означает, что эта пометка дает точную длину кратчайшего пути от S к рассматриваемой вершине

Рассмотрим суть алгоритма Дейкстры.

Пусть l(X_i) - пометка вершины X_i.

Присваивание начальных значений

Шаг первый

Положить 1(S) = 0 и считать эту пометку постоянной.

Положить l(X_i) = ∞ для всех X_i ≠ S, и считать эти пометки временными.

Положить р = S,

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

Обновление пометок

Шаг второй

Для Х є Г(р), пометки которых временные, изменить их в соответствии со следующим выражением:

l(X_i)=min[ l(X_i); l(p)+c(p,X_i) ] (1)

Превращение пометки в постоянную

Шаг третий

Среди всех вершин с временными пометками найти такую, для которой l(X_i*)=min[l(X_i)]

Шаг четвертый

Считать пометку вершины X_i* постоянной и положить p =X_i*.