Метод Дейкстры

Метод применяется для поиска кратчайшего пути m[ s, t ] из источника s в сток t на графе G = (X, U) в том случае, когда длина любой дуги неотрицательна, т. е. l (x_i, x_j) > 0 для всех (x_i, x_j) Î U. Алгоритм Дейкстры легко модифицируется для решения задачи поиска всех кратчайших путей m[ s, x_i ], x_i Î X \ s.

Этот метод основан на приписывании вершинам графа временных пометок l(x_i), x_i Î X. Величина каждой временной пометки l(x_i) опреде­ляет верхнюю границу длины пути m[ s, x_i ]. С помощью итерацион­ной процедуры значения l(x_i) постепенно уменьшаются, причем на каждой итерации одна из вершин графа получает постоянную пометку l^*(x_i). Постоянная пометка, в отличие от временной, дает не оценку, а истинное значение длины кратчайшего пути m[ s, x_i ].

Формальная схема алгоритма Дейкстры может быть представлена в следующем виде.

Алгоритм 1.2 (метод Дейкстры)

Данные: орграф G = (X, U), имеющий n вершин, с выделенным источником s и стоком t (s, t Î X); веса дуг l (x_i, x_j) ³ 0 для всех (x_i, x_j) Î U.

Результаты: длина l^*(t) кратчайшего пути m[ s, t ].

Шаг 1 (присвоение начальных значений)

Определить постоянную пометку l^*(s) = 0 и временные пометки
l(x_i) = ¥ для всех x_i Î X \ s. Зафиксировать вершину p = s, получившую постоянную пометку.

Шаг 2 (изменение пометок вершин)

Для всех x_i Î Г(p), имеющих временные пометки, вычислить новые значения l(x_i) по формуле:

l(x_i) = min [l(x_i), l(p) + l (p, x_i)].

Шаг 3 (определение постоянной пометки)

Среди всех вершин x_i Î X, имеющих временные пометки, найти x_k, для которой значение l(x_k) минимально, т. е.

,

где T Ì X - подмножество вершин с временными пометками. Пометку вершины x_k считать постоянной l^*(x_k) = l(x_k) и присвоить p = x_k.

Шаг 4 (проверка условия окончания)

Если p = t, то l^*(p) есть длина кратчайшего пути m[ s, t ]. Конец алгоритма. Если p ¹ t, то переход к шагу 2.

Чтобы использовать метод Дейкстры для поиска всех кратчайших путей m[ s, x_i ], x_i Î X \ s, достаточно изменить условие окончания итерационного процесса. В этом случае последний шаг алгоритма формулируется следующим образом.

Шаг 4¢ (условие окончания алгоритма 1.2

для поиска путей m[ s, x_i ], x_i Î X \ s)

Если все вершины , получили постоянные пометки l^*(x_i), то конец алгоритма. Иначе выполнить переход к шагу 2.

Алгоритм Дейкстры гарантирует получение оптимального результата. Доказательство этого факта приводится в работах [5, 6].

Если производится поиск всех путей m[ s, x_i ], x_i Î X \ s, для полного связного орграфа с n вершинами, то при работе алгоритма на шаге 2 выполняются n (n - 1)/2 операций сложения и сравнения, на шаге 3 - еще
n (n - 1)/2 операций сравнения. Кроме того, для определения подмноже­ства вершин с временными пометками (шаги 2, 3) требуется также n (n - 1)/2 операций сравнения. Таким образом, в целом выполняется 3/2 n (n - 1) операций, что соответствует оценке трудоемкости O (n ²).

Для алгоритма поиска кратчайшего пути m[ s, t ] число операций 3/2 n (n - 1) является предельным и достигается только в случае, когда сток t получает постоянную пометку последним из всех вершин.

Пример 1.2. Работа алгоритма Дейкстры для поиска кратчайшего пути m[ x ₁, x ₅] в графе G = (X, U), приведенном на рис. 1.5, показана в табл. 1.3, где значения постоянных пометок и соответствующие вершины выделены символом "^*".

Рис. 1.5. Представление графа для примера 1.2

Таблица 1.3

Результаты работы алгоритма Дейкстры (пример 1.2)

Для построения пути кратчайшей длины из x ₁ в x ₅ используется условие (1.2). Предпоследняя вершина x ^(k) этого пути входит в подмножество Г^-1(x ₅) = { x ₄, x ₆} и удовлетворяет соотношению

l^*(x ^(k)) + l (x ^(k), x ₅) = l^*(x ₅),

которое выполняется для x ^(k) = x ₆. Далее определяется следующая вершина x ^{(k -1)} Î Г^-1(x ₆) и т.д. Окончательно кратчайший путь имеет вид:

m(x ₁, x ₅) = (x ₁, x ₂, x ₄, x ₃, x ₆, x ₅).

У П Р А Ж Н Е Н И Я

1.24. Сколько итераций требуется для определения всех постоянных пометок вершин в алгоритме Дейкстры?

1.25. Почему метод Дейкстры поиска кратчайшего пути на графе не допускает отрицательных значений весов дуг?

1.26. Модифицировать алгоритм 1.2 таким образом, чтобы поиск кратчайшего пути производился с использованием пометок вида [l(x_i), m_i ], которые описаны в разделе 1.2.

1.27. Разработать программу поиска кратчайшего пути на графе по алгоритму 1.2.

1.28. Разработать программу поиска кратчайшего пути на графе по алгоритму, полученному при выполнении упражнения 1.26.

1.29. Получить (машинное) решение для задачи поиска всех кратчайших путей m[ x ₁, x_j ], , от вершины x ₁ ко всем остальным вершинам графа, показанного на рис. 1.6.

Замечание: значения постоянных пометок указаны около соответствующих вершин графа.

Рис. 1.6. Представление графа для упражнения 1.29