Алгоритм Дейкстры

(нахождение кратчайшего пути от одного узла до всех остальных)

Шаг 0. Каждому узлу (i = 1,2,..., п-1) присвоить временную метку . (если нет дуги, соединяющей и полагаем )

Шаг 1. Среди всех временных меток выбрать . Заменить на . Если нет временных меток, остановиться.

Шаг 2. Пусть — узел, только что получивший постоянную метку на шаге 1. Изменить временные метки соседей узла в соответствии со следующим правилом: . Перейти к шагу 1.

Пример 2.1. Рассмотрим сеть, показанную на рис. 2, где числа являются длинами дуг.

Будем изображать временные метки внутри каждого узла, а когда метка превращается в постоянную, будем помечать число звездочкой. Когда дуга применяется в некотором кратчайшем пути, будем изображать ее жирной линией.

Шаг 0. Все узлы получают временные метки, равные , а узел – постоянную метку 0. Это показано на рис. 3.

Шаг 1. Среди всех временных меток минимальное значение 2 имеет метка узла , поэтому получает постоянную метку.

Рис. 2

Рис. 3.

Шаг 2. Узел имеет соседей и .

.

.

Результат показан на рис. 4.

Рис. 4.

Шаг 1. Среди всех временных меток наименьшую метку 3 имеет узел . Поэтому получает постоянную метку.

Шаг 2. Соседями узла являются , . (Узел тоже соседний, но он стал постоянным и поэтому исключается.)

.

Шаг 1. Узел V₁ получает постоянную метку 4.

Шаг 2. . Это показано на рис. 5.

Шаг 1. V₄ получает постоянную метку 5.

Рис. 5.

Шаг 2. .

Шаг 1. V₆получает постоянную метку 11.

Шаг 2.

Шаг 1. V₅получает постоянную метку 13.

Шаг 2.

Шаг 1. V₇получает постоянную метку 14.

Окончательный результат показан на рис. 6.

Мы вычислили кратчайшие расстояния от V₀ до всех остальных узлов сети, но не нашли кратчайших путей, на которых достигаются эти расстояния.

Способ проследить промежуточные узлы:

Если узлу V_j приписана постоянная метка, то можно просмотреть все соседние узлы и найти среди них тот, метка которого отличается от метки узла V_j в точности на длину соединяющей их дуги. Таким образом, мы можем для каждого узла проследить в обратном направлении путь из начала в этот узел. На рис. 7 каждому узлу приписаны два числа. Первое число — постоянная метка, указывающая истинное кратчайшее расстояние от начала до этого узла, второе число указывает последнюю промежуточную вершину кратчайшего пути.

Рис. 6.

Рис. 7.

Сложность алгоритма. Так как алгоритм состоит из сравнений и сложений, подсчитаем количество сравнений и сложений.

Имеется n - 2 сравнений при первом проходе, п - 3 сравнений при втором проходе и т. д., так что всего имеется (n - 2) + (n - 3) + . . . + 1 = (n - 1)(n - 2)/2 сравнений на шаге 1. Аналогично, имеется (n - 1)(n - 2)/2 сложений и столько же сравнений на шаге 2. Поэтому, трудоемкость алгоритма есть О(n²). Так как в сети с n узлами имеется О(n²) дуг и каждая дуга должна быть рассмотрена хотя бы один раз, то не будет рискованным сказать, что не существует алгоритма, требующего в общем случае O(n log n) шагов.