Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 21. Кратчайшие пути. Метод выбора для решения задачи поиска кратчайших путей для всех пар в насыщенных графах, который был разработан Р
|
|
Метод выбора для решения задачи поиска кратчайших путей для всех пар в насыщенных графах, который был разработан Р. Флойдом (R. Floyd), в точности совпадает с методом Уоршалла за исключением того, что вместо использования операции логического или для отслеживания существования путей, он проверяет расстояния для каждого ребра, чтобы определить, является ли это ребро частью нового, более короткого пути. Действительно, как уже отмечалось, алгоритмы Флойда и Уоршалла идентичны при соответствующей абстрактной постановке (см. разделы 19.3 и 21.1).
Программа 21.5. Алгоритм Флойда для поиска всех кратчайших путей___________________
Эта реализация интерфейса из программы 21.2 использует алгоритм Флойда, представляющий собой обобщение алгоритма Уоршалла (см. программу 19.3), который отыскивает кратчайшие пути между каждой парой точек вместо того, чтобы только проверять их существование.
После инициализации матриц расстояний и путей ребрами графа мы выполняем последовательность операций ослабления для вычисления кратчайших путей. Алгоритм прост в реализации, но проверка того, что он вычисляет кратчайшие пути более сложна (см. рассуждения по тексту раздела).
template < class Graph, class Edge> class allSP { const Graph & G;
vector < vector < Edge *> > p; vector < vector < double> > d; public:
allSP(const Graph & G): G(G), p(G.V()), d(G.V()) { int V = G.V();
for (int i = 0; i < V; i++)
{ p[i].assign(V, 0); d[i].assign(V, V); } for (int s = 0; s < V; s++) for (int t = 0; t < V; t++) if (G.edge(s, t)) { p[s][t] = G.edge(s, t);
d[s][t] = G.edge(s, t)-> wt(); } for (int s = 0; s < V; s++) d[s] [s] = 0; for (int i = 0; i < V; i++) for (int s = 0; s < V; s++) if (p[s][i])
for (int t = 0; t < V; t++) if (s! = t)
if (d[s][t] > d[s][i] + d[i][t]) { p[s][tj = p[s][i];
d[s][t] = d[s][i] + d[i][t]; } } Edge *path(int s, int t) const
{ return p[s][t]; } double dist(int s, int t) const { return d[s][t]; }
>;
Программа 21.5 представляет функцию АТД поиска кратчайших путей для всех пар, которая реализует алгоритм Флойда. Она явно использует матрицы из раздела 21.1 как приватные элементы данных: вектор V на V векторов d для матрицы расстояний и еще один вектор V на V векторов р для таблицы путей. Для каждой пары вершин s и t конструктор заполняет d[s][t] длинами кратчайших путей из s в t (возвращаемых функцией-эле-
Часть 5. Алгоритмы на графах
ментом dist), a p[s][t] — индексами следующей вершины на кратчайшем пути из s в t (возвращаемых функцией-элементом path). Реализация основывается на операции ослабления пути, которая рассматривалась в разделе 21.1.
Свойство 21.8. С помощью алгоритма Флойда можно найти все кратчайшие пути в сети за время, пропорциональное V3.
Доказательство: Время выполнения можно вычислить непосредственно из самого кода. Доказательство корректности алгоритма мы проводим точно таким же образом, т.е. методом индукции, как это делалось в отношении алгоритма Уоршалла. /-тая итерация цикла вычисляет кратчайший путь из s в t в сети, которая не включает никаких вершин с индексами больше / (кроме, возможно, конечных точек s и t). Полагая, что это утверждение истинно для /-той итерации, мы покажем, что оно истинно для (/+1)-й итерации цикла. Любой кратчайший путь из s в tкоторый не включает никаких вершин с индексами большими /+1, есть либо (i) путь из s в t, не включающий никаких вершин с индексами больше / и имеющий длину d[s][t], который был найден на предыдущей итерации цикла по предположению индукции, либо (//) заключает в себе пути из s в # и из t в /, ни один из которых не включает никаких вершин с индексами больше /, и в этом случае внутренний цикл устанавливает d[s][t]. ■
На рис. 21.14 показана детальная трассировка выполнения алгоритма Флойда для нашей типовой сети. Если отметить каждый пустой элемент как 0 (указав на отсутствие ребра), а каждый непустой элемент — как 1 (указав на наличие ребра), то эти матрицы описывают операции алгоритма Уоршалла точно так же, как это было сделано на рис. 19.15. В случае алгоритма Флойда непустые элементы указывают на большее, нежели существование пути, — они дают информацию об известном кратчайшем пути. Элемент в матрице расстояний представляет длину известного кратчайшего пути, который соединяет вершины, соответствующие данной строке и столбцу; соответствующий элемент в матрице путей дает следующую вершину на этом пути. По мере заполнения матриц ненулевыми элементами, алгоритм Уоршалла производит перепроверку, соединяют ли новые пути те пары вершин, которые уже соединены известными путями. В отличие от этого, алгоритм Флойда должен проверить (и при необходимости обновить) каждый новый путь, чтобы убедиться, что его использование приведет к более короткому пути.
Сравнивая граничные оценки для худшего случая по времени исполнения алгоритмов Дейкстры и Флойда, мы можем прийти к тому же результату для алгоритмов поиска кратчайших путей для всех пар, как это делалось для соответствующих алгоритмов транзитивного замыкания в разделе 19.3. Выполнение алгоритма Дейкстры на каждой вершине, очевидно, является подходящим методом для разреженных сетей, поскольку время счета близко к VE. По мере возрастания плотности графа, конкурентоспособным становится алгоритм Флойда, который всегда требует времени, пропорционального V3 (см. упражнение 21.67); он широко используется ввиду простоты реализации.
Более существенное различие между алгоритмами, которое подробно рассматривается в разделе 21.7, состоит в том, что алгоритм Флойда эффективен даже на сетях, которые имеют отрицательные веса (при условии, что нет отрицательных циклов). Как отмечалось в разделе 21.2, в таких графах метод Дейкстры не обязательно находит кратчайшие пути.
Глава 21. Кратчайшие пути
|
РИСУНОК 21.14. АЛГОРИТМ ФЛОЙДА Эта последовательность показывает построение матриц кратчайших путей для всех пар с помощью алгоритма Флойда. Для i от 0 до 5 (сверху вниз), для всех s и t мы рассматриваем все пути из s в t, не имеющие промежуточных вершин, больших i (заштрихованные вершины). Вначале единственными такими путями будут ребра сети, так что матрица расстояний (в центре) — это матрица смежности графа, а в матрице путей (справа) для каждого ребра s-t установлено p[s][t] = t. Для вершины 0 (вверху) алгоритм находит, что 3-0-1 короче, чем сигнальное значение, которое говорит об отсутствии ребра 3-1, и соответствующим образом обновляет матрицы. Он не делает этого для такого пути, как, например, 3-0-5,
который не короче известного пути 3-5. Далее алгоритм рассматривает пути, проходящие через O и l (второй сверху) и находит новые более короткие пути 0-1-2, 0-1-4, 3-0-1-2, 3-0-1-4 и 5-1-2. Третий ряд сверху показывает обновления, соответствующие более коротким путям через 0, 1, 2 и т.д.
Черные числа, находящиеся поверх серых в матрицах, указывают на ситуации, где алгоритм находит более короткий путь, чем найденный раньше. Например, 0.91 находится поверх 1.37 в строке 3 и столбце 2 внизу схемы, поскольку алгоритм нашел, что путь 3-5-4-2 оказался короче пути 3-0-1-2.
310 Часть 5, Алгоритмы на графах
Классические решения описанной задачи поиска кратчайших путей для всех пар предполагают, что мы располагаем доступным пространством памяти, достаточным для хранения матриц расстояний и путей. Огромные разреженные графы, для которых мы не можем позволить себе иметь произвольные матрицы V на V, представляют еще одну интересную и перспективную область. Как было показано в главе 19, имеется одна открытая задача, связанная со сведением расхода этого пространства к величине, пропорциональной V, при сохранении поддержки линейного времени запросов на длины кратчайших путей. Мы выяснили, что сходные проблемы трудноразрешимы даже для более простой задачи достижимости (где мы в учебных целях удовлетворились линейным временем независимо от того, есть ли вообще какой-либо путь, соединяющий данную пару вершин), так что нельзя ожидать простого решения задачи кратчайших путей для всех пар. Действительно, количество различных кратчайших длин путей в общем случае пропорционально V2 даже для разреженных графов. Эта величина в некотором смысле служит мерой количества информации, которую требуется обработать, и, возможно, указывает, что если существует ограничение по пространству памяти, то следует ожидать больших временных затрат на каждый запрос (см. упражнения 21.48-21.50).