Алгоритм Дейкстры отыскания кратчайших расстояний на графе.

Алгоритм Дейкстры применяется для случая, когда c_v> 0. В нем каждая вершина может быть:

a) непомеченной,

b) помеченной временной пометкой,

c) помеченной постоянной пометкой.

Вершина i непомечена, если для нее не найдено ни одного пути из вершины н, помечена временной пометкой, если из вершины н найден путь и величина W_i есть верхняя оценка кратчайшего расстояния от н до i (и на последующих итерациях величина W_i может быть уточнена вплоть до кратчайшего расстояния от н до i). Помечена постоянной пометкой, если W_i из верхней оценки стала кратчайшим расстоянием от н до i. Алгоритм первого этапа заканчивает работу, если вершина к стала помеченной постоянной пометкой, в этом случае W_к стало равным кратчайшему расстоянию от н до к.

 

Первый этап.

0– шаг. Для всех iÎE\ { н } полагаем W_i = M, эти вершины считаем непомнеченными, для i = н полагаем W_i =0, эту вершину считаем помеченной временной пометкой,

k– ый шаг. Ищем , где минимум берется переменной i среди все временно помеченных вершин. Вершину j помечаем постоянной пометкой. Если j = к, то найдено кратчайшее расстояние до этой вершины, и переходим к восстановлению кратчайшего пути, выполняемого на втором этапе, в противном случае «просматриваем» вершину j, т.е. для всех выполняем:

a) определяем i = h ₂(v),

b) полагаем W_i =min(W_i, c_v+W_j), помечаем эту вершину временной пометкой и переходим к выполнению (K+ 1) шага.

Второй этап. (восстановление кратчайшего пути)

Так как движение идет от конца пути к началу, то применим обратный отсчет шагов, в нем начальный шаг N =| E |.

N – шаг. Полагаем ;

k– ый шаг (k = N –1, N –2,…). Среди ищем , для которой

, полагаем . Если , то алгоритм заканчивает работу, в противном случае переходим к выполнению(k– 1) –го шага.

Пусть k номер шага, на котором остановился алгоритм второго этапа, тогда решение задачи имеет вид .

Замечание. Для отыскания кратчайшего расстояния между двумя вершинами достаточно, чтобы только конечная вершина получила постоянную пометку. Если требуется найти кратчайшее расстояние от начальной вершины до всех остальных, то следует выполнять алгоритм до тех пор, пока все вершины не окажутся помечеными постоянной пометкой.

Пример. Рассмотрим вновь пример, который приведен на следущем рисунке:

0–й шаг. Все вершины непомечены, в них в квадратах около вершин записаны «¥», кроме вершины 1, около нее в квадрате записано «0». Далее будем считать, что если в прямоугольнике не «¥», то вершина непомечена, если это число не ¥, вершина помечена временной пометкой, если квадрат затемнен, то пометка постоянная.

2–й шаг. Среди всех временно помеченных вершин выбираем вершину с наименьшей величиной пометки, это вершина 1, она становится постоянно помеченной, из нее по инцидентным дугам просматриваются вершины 2,4,3. Для них соответственно , , . Эти значения вносим в рисунок

2–й шаг. Повторяем процедуру, аналогичную шагу 2, но теперь для вершины 1.

Заметим, что величина пометки вершины 4 уменьшилась после просмотра вершины 1.

3–й шаг. Просматриваем вершину 4, так как у нее наименьшая пометка, будем иметь

 

4–й шаг. Просматриваем вершину 3 (можно и 5,), при ее просмотре в других вершинах ничего не изменяется.

5–й шаг. Просматриваем вершину 5, получим

6–й шаг. Постоянно помеченной вершиной становится вершина 6. До нее найдено кратчайшее расстояние. Оно равно 4.

Работу второго этапа также продемонстрируем на рисунке. Среди дуг, входящих в вершину 6, выделим дугу, для которой выполняется равненство . Таковой является дуга v₁₀. Для нее 3+1=4, вершина – начало этой дуги равно 5.

Теперь эту же процедуру проведем для вершины 5, и так далее. Получим путь, изображенный на рисунке

Самостоятельная работа 16.

Для графа, приведенного на рисунке найти кратчайшие расстояния между вершин с номерами 1 и 9 тремя способами.

Варианты заданий