![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 21. Кратчайшие пути. Метод выбора для решения задачи поиска кратчайших путей для всех пар в насыщенных графах, который был разработан Р
Программа 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]; } >;
Часть 5. Алгоритмы на графах
Свойство 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, Алгоритмы на графах
|