Глава 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. Алгоритмы на графах

Глава 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, при сохранении поддержки линейного времени запросов на длины кратчайших путей. Мы выяснили, что сходные проблемы трудноразрешимы даже для более простой задачи достижимости (где мы в учебных целях удовлетворились линейным вре­менем независимо от того, есть ли вообще какой-либо путь, соединяющий данную пару вершин), так что нельзя ожидать простого решения задачи кратчайших путей для всех пар. Действительно, количество различных кратчайших длин путей в общем случае про­порционально V² даже для разреженных графов. Эта величина в некотором смысле слу­жит мерой количества информации, которую требуется обработать, и, возможно, указы­вает, что если существует ограничение по пространству памяти, то следует ожидать больших временных затрат на каждый запрос (см. упражнения 21.48-21.50).