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

Задача: задан ориентированный «взвешенный» граф. Найти кратчайший по длине путь между двумя заданными вершинами.

«Взвешенный» – каждой дуге сопоставлено некотор.отриц.число.

Обозначим через u_i кратчайшее расстояние от исходного узла 1 до узла i, через d_ij - длину ребра (i, j).

Тогда для узла j определим метку [u_j, i] следующим образом: [u_j, i] = [u_i + d_ij, i], d_ij >= 0.

Метки узлов могут быть двух типов: временные и постоянные.

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

Шаг i. а) Вычисляются временные метки [u_i + d_ij, i] для всех узлов j, которые можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку [u_j, k], полученную от другого узла k, и если u_i + d_ij < u_j, тогда метка [u_j, k] заменяется на [u_i + d_ij, i].

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

Шаг 0. Назначаем узлу 1 постоянную метку [0, -].

Шаг 1. Из узла 1 можно достичь узлов 2 и 3. Вычисляем метки для этих узлов, в результате получаем следующую таблицу меток:

Узел Метка Статус метки 1 [0, -] Постоянная 2 [0 + 100, 1] = [100, 1] Временная 3 [0 + 30, 1] = [30, 1] <-Временная

Третий узел имеет наименьшее значение расстояния (u₃ = 30). Поэтому статус метки этого узла изменяется на "постоянная";.

Шаг 2. Из узла 3 (последнего узла с постоянной меткой) можно попасть в узлы 4 и 5. Получаем следующий список узлов:

Узел Метка Статус метки 1 [0, -] Постоянная 2 [100, 1] Временная 3 [30, 1] Постоянная 4 [30 + 10, 3] = [40, 3] <-Временная 5 [30 + 60, 3] = [90, 3] Временная

Временный статус метки [40, 3] узла 4 заменяется на постоянный (u₄ = 40).

Шаг 3. Из узла 4 можно достичь узлов 2 и 5. После вычисления меток получим следующий их список:

Узел Метка Статус метки 1 [0, -] Постоянная 2 [40 + 15, 4] = [55, 4] <-Временная 3 [30, 1] Постоянная4 [40, 3] Постоянная 5 [90, 3] или [40+50, 4]=[90,4] Временная

Временная метка [100, 1], полученная узлом 2 на втором шаге, изменена на [55, 4]. Это указывает на то, что найден более короткий путь к этому узлу (проходящий через узел 4). На третьем шаге узел 5 получает две метки с одинаковым значением расстояния u₅ = 90.

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

Шаг 5. С временной меткой остается только узел 5, но так как из этого узла нельзя попасть ни в какой другой, ему присваивается постоянный статус и процесс вычислений заканчивается.

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

(2) -> [55, 4] -> (4) -> [40, 3] -> (3) -> [30, 1] ->(1)

Между узлами (2) и (1): [55, 4].