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

Этот алгоритм требует, чтобы длины всех путей были положительны(это выполняется в сетях передачи данных).Объём вычислений в худшем случае для этого алгоритма значительно меньше, чем у алгоритма Беллмана-Форда. Основная идея алгоритма состоит в том, чтобы отыскивать кратчайшие пути в порядке возрастания длины пути. Кратчайшим из всех кратчайших путей от узла 1 является путь, состоящий из одной дуги, соединяющий узел 1 с ближайшим соседним узлом. Следующим кратчайшим среди кратчайших путей должен быть либо путь из одной дуги к следующему ближайшему соседу узла 1,либо кратчайший путь из двух дуг, проходящей через узел, выбранный на первом шаге, и т.д. Для формального описания алгоритма каждый узел i имеет метку ,означающую оценку длины кратчайшего пути от узла 1.Когда оценка становиться неизменной, считается, что узел окончательно помечен. Множество окончательно помеченных узлов обозначим через P. Узел, который будет добавлен на очередном шаге к P, является ближайшим к узлу 1 среди всех узлов, ещё не вошедших в P, так как кратчайшее расстояние получается минимизацией по j P величины .Вычислительная сложность алгоритма будет порядка 0().

Рис.8.6 иллюстрирует работу алгоритм Дийкстра, а также алгоритма Беллмана-Форда.

3

1 2

1 1

4 4

1

Беллман-Форд

Дийкстра

=4 =3 =3

=6 =5

=4 =2 =3 =2 =3 =2

P={1,2} P={1,2,5} P={1,2,3,4,5}

Рис. 8.6

Формально алгоритм работает следующим образом.

Сначала P={1}, =0 и для j≠1.

Шаг 1 (поиск следующего ближайшего узла).Найти i P такой, что

Положить P:=P {i}.Если P содержит все узлы, то на этом работа алгоритма заканчивается.

Шаг 2 (обновление меток).Для всех j P положить .

Перейти к шагу 1.