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

В процессе выполнения этого алгоритма при переходе от узла к следующему узлу используется специальная процедура пометки ребер. Обозначим через кратчайшее расстояние от исходного узла 1 до узла , через — длину ребра . Тогда для узла определим метку следующим образом:

, .

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

Вычислительная схема алгоритма состоит из следующих шагов.

Шаг 0. Исходному узлу (узел 1) присваивается метка . Полагаем .

Шаг 1.

a) Вычисляются временные метки для всех узлов , которые можно достичь непосредственно из узла и которые не имеют постоянных меток. Если узел уже имеет метку , полученную от другого узла , и если тогда метка заменяется на .

b) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка с наименьшим значением расстояния среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем и повторяем шаг .