Централизованные алгоритмы нахождения кратчайшего пути

Наиболее распространенными стандартными алгоритмами решения задачи нахождения кратчайшего пути на графе являются: алгоритм Беллмана-Форда, алгоритм Дийкстра и алгоритм Флойда-Уоршела [1],[10].

Первые два алгоритма находят кратчайшие пути от узла источ­ника ко всем другим узлам, а третий алгоритм находит кратчайшие пути от всех узлов ко всем другим узлам.

Рассмотрим в качестве примера алгоритм Дийкстра. Этот алго­ритм требует, чтобы длины (веса) всех ребер были положительны. Объем вычислений для этого алгоритма значительно меньше, чем у алгоритма Беллмана-Форда.

Основная идея алгоритма - отыскание кратчайших путей в по­рядке возрастания длины пути.

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

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

Полагаем Р = {1}, D_i = 0 D_i = d_1j " j¹1 при наличии cвязи узла c1.

Шаг I. Поиск следующего ближайшего узла.

Находим узел iÏ P такой, что D_i min_jÏP D_j

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

Шаг 2. Обновление меток.

Для всех jÏP положить D_i min {D_j, D_i + d_ij}

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

Пример использования алгоритма Дийкстра приведен на рис. 2.2.

Число операций, выполняемых алгоритмом Дийкстра на каждом шаге, пропорционально N, а шаги итерируются N-1 раз. Таким обра­зом, объем вычислений в худшем случае пропорционален N², а не N³, как у алгоритма Беллмана-Форда.

Дата добавления: 2015-07-25