Централизованные алгоритмы нахождения кратчайшего пути
Методы маршрутизации, основанные на выборе кратчайшего пути.
Проблема маршрутизации в информационных сетях.
Конкретный метод маршрутизации обычно реализуется в рамках протокола сетевого уровня, который управляет пакетами при их движении по сети до места назначения.
Большинство реальных алгоритмов маршрутизации, так или иначе, базируются на выборе кратчайшего пути в графе с той или иной метрикой. При этом определение кратчайшего пути может осуществляться, как централизованно, по имеющейся информации о состоянии сети, так и децентрализовано (распределенно) на основе имеющейся в узле информации о состоянии ближайших соседей, когда структура всей сети неизвестна (метод "рельефа").
Наиболее распространенными стандартными алгоритмами решения задачи нахождения кратчайшего пути на графе являются: алгоритм Беллмана-Форда, алгоритм Дийкстра и алгоритм Флойда-Уоршела [1],[10].
Первые два алгоритма находят кратчайшие пути от узла источника ко всем другим узлам, а третий алгоритм находит кратчайшие пути от всех узлов ко всем другим узлам.
Рассмотрим в качестве примера алгоритм Дийкстра. Этот алгоритм требует, чтобы длины (веса) всех ребер были положительны. Объем вычислений для этого алгоритма значительно меньше, чем у алгоритма Беллмана-Форда.
Основная идея алгоритма - отыскание кратчайших путей в порядке возрастания длины пути.
Чтобы формально описать процедуру нахождения кратчайшего пути, будем считать, что каждый узел i имеет метку Di , означающую текущую оценку длины кратчайшего пути от узла 1 . Когда оценка становится неизменной, будем считать, что узел окончательно помечен, и множество окончательно помеченных узлов обозначим через Р. Узел, который будет добавлен на очередном шаге к Р , является ближайшим к узлу 1 среди всех узлов, еще не вошедших в Р.
Алгоритм работает следующим образом.
Полагаем Р = {1} , Di = 0 Di = d1j " j¹1 при наличии cвязи узла c1 .
Шаг I. Поиск следующего ближайшего узла.
Находим узел iÏ P такой, что Di =
Полагаем Р: PÈ{1}. Еcли Р содержит вcе узлы, то на этом работа алгоритма заканчивается.
Шаг 2. Обновление меток.
Для всех jÏP положить Di = min{Dj, Di + dij}
Перейти к шагу I.
Пример использования алгоритма Дийкстра приведен на рис. 21.
Число операций, выполняемых алгоритмом Дийкстра на каждом шаге, пропорционально N , а шаги итерируются N-1 раз. Таким образом, объем вычислений в худшем случае пропорционален N2, а не N3 , как у алгоритма Беллмана-Форда.