Нахождение кратчайшего пути в графе. Алгоритм Дейкстры

Граф – это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.

Пусть дан граф, каждой дуге которого приписан вес. Задача о нахождении кратчайшего пути состоит в нахождении кратчайшего пути от заданной начальной вершины до заданной конечной вершины, при условии, что такой путь существует.

Алгоритм Дейкстры — алгоритм поиска кратчайшего пути во взвешенном графе между двумя заданными вершинами s и t при неотрицательных весах всех дуг.

Пусть s - начальная вершина пути, t - конечная.

На каждой итерации алгоритма каждая вершина x_i графа имеет метку l (x_i), которая может быть постоянной или временной. В первом случае l (x_i) является длиной кратчайшего (s, x_i)-пути; во втором случае l (x_i) - длина кратчайшего (s, x_i)-пути, проходящего через вершину x_i и вершины с постоянными метками. Таким образом временная метка l (x_i), является оценкой сверху для длины кратчайшего (s, x_i)-пути, и, став на некоторой итерации постоянной, она остается такой до конца работы алгоритма.

Кроме l (x_i), с вершинами графа связывается еще одна метка Q(x_i).На каждой итерации Q(x_i) является номером вершины, предшествующей х_i в кратчайшем (s, x_i)-пути.

После того, как последняя вершина t получила постоянную метку, с помощью меток Q(x) легко указать последовательность вершин, составляющих кратчайший (S,t)-путь:

(s..., Qⁿ(t)..., Q(Q(t)), Q(t),t),

Qⁿ(t)= Q(Q(...Q(t)) (n раз).

Перед началом работы алгоритма начальная вершина s имеет постоянную метку l (s)=0, а метки всех остальных вершин равны бесконечности (∞) и являются временными. Обозначим через p последнюю из вершин, получивших постоянную метку.

Алгоритм Дейкстры включает следующие шаги:

1. Положить l (s)=0 и считать эту метку постоянной. Положить l (x_i)= ∞ для всех x_i ¹ s, и считать эти метки временными. p = s.

2. Обновление пометок. Для всех вершин x_i Î Г(p), пометки которых временные, изменить пометки в соответствии с правилом:

l (x_i)=min { l (x_i), l (p) +w(p, x_i) }.

Если l (x_i)> l (p) +w(p, x_i), то Q(x_i) = p.

3. Если l (x_i)= ∞ для всех вершин x_i, пометки которых временные, то в исходном графе отсутствуют пути из вершины s в вершины с временными метками. Останов алгоритма. В противном случае переход к шагу 4.

4. Превращение пометок в постоянные. Среди всех вершин с временными метками найти такую вершину x_i^*, для которой l (x_i^*) = min l (x_i) (метка минимальная) и считать эту пометку постоянной. Положить p=x_i^*. Пометку Q(x_i^*) также считать постоянной.

5. Если p ¹ t, перейти к шагу 2, а если p = t, то l (p) - длина кратчайшего пути из s в t.

После определения длины кратчайшего пути сам кратчайший путь восстанавливается по постоянным меткам Q(x_i).