Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями

Задача поиска кратчайших путей между всеми парами (APSP) заключается в нахождении кратчайших путей между всеми парами вершин в ориентированном графе с ребрами неотрицательной действительной стоимости. Основное внимание уделяется кратчайшим расстояниям между вершинами, поскольку кратчайшие пути могут быть найдены с незначительным возрастанием стоимости. Классические алгоритмы решают задачу нахождения кратчайших путей между всеми парами вершин за кубическое время – <math>O(n^3) \, </math>. Наша задача заключается в достижении меньшего времени исполнения алгоритма для графа с небольшими целочисленными стоимостями ребер.

Для неориентированных графов с единичной стоимостью ребра Зейделем было доказано время исполнения <math>\tilde{O}(n^{\omega}) \, </math> [7].

Если стоимости дуг ограничены положительным целым числом M, можно разработать более удачный алгоритм, что было показано Такаокой в [9]. Вкратце рассмотрим алгоритм Романи [6] для произведения матриц расстояния.

Заметим, что граница M была заменена на <math>\ell</math>M в произведении матриц расстояния на первом этапе. Игнорируя полилогарифмические коэффициенты, получаем время исполнения для первого этапа – <math>\tilde{O}(n^{\omega} r^2 M) \, </math>. Мы предполагаем, что M соответствует <math>O(n^k) \, </math> для некоторого константного k. Сравнивая эту сложность со сложностью второго этапа, <math>O(n^3/r) \, </math>, получаем полное время вычисления <math>\tilde{O}(n^{(6 + \omega)/3} M^{1/3}) \, </math> при выборе <math>r = O(n^{(3 - \omega)/3} M^{-1/3}) \, </math>. Чтобы время исполнения оказывалось меньше кубического, значение M должно почти совпадать с <math>O(n^{0.624}) \, </math>.

Цвик улучшил алгоритм Алона-Галила-Маргалита в нескольких отношениях. Самым серьезным улучшением стало снижение времени нахождения кратчайших путей между всеми парами с <math>O(n^{2.688}) \, </math> до <math>O(n^{2.575}) \, </math> для дуг единичной стоимости. Наибольшее ускорение в алгоритме Алона-Галила-Маргалита [1] было достигнуто в быстрой операции булева произведения матриц, а в алгоритме Такаоки [9] – в быстром умножении матриц расстояния по Романи; в обоих случаях мы имели дело с быстрым матричным умножением квадратных матриц.

В данном разделе «ускорителем» служит алгоритм быстрого умножения матриц расстояния по Романи, созданный на основе алгоритма быстрого умножения прямоугольных матриц, разработанного Копперсмитом [4] и Хуангом и Пэном [5]. Пусть <math>\omega(p, q, r) \, </math> – порядок временной сложности при умножении матриц <math>(n^p, n^q) \, </math> и <math>(n^q, n^r) \, </math>. Предположим, что произведение матриц (n, m) и (m, n) может быть вычислено за <math>O(n^{\omega (1, \mu, 1)}) \, </math> арифметических операций, где <math>m = n^{\mu} \, </math> и <math>0 \le \mu \le 1 \, </math>. Нам известно следующее: <math>O(n^{\omega( 1, 1, 1)}) = O(n^{2.376}) \, </math> и <math>O(n^{\omega (1, 0.294, 1)}) = \tilde{O}(n^2) \, </math>. Для вычисления произведения квадратных матриц (n, n) требуется <math>n^{1 - \mu} \, </math> операций матричного умножения, что дает время исполнения <math>O(n^{(\omega(1, \mu, 1) + 1 - \mu}) \, </math>, которое можно преобразовать в <math>O(n^{2 + \mu}) \, </math>, где <math>\mu \, </math> удовлетворяет равенству <math>\omega(1, \mu, 1) = 2 \mu + 1 \, </math>. На данный момент лучшее известное значение <math>\mu \, </math> составляет <math>\mu = 0.575 \,</math>, так что временная граница превращается в <math>O(n^{2.575}) \, </math> – это значение уступает <math>O(n^{2.376}) \, </math>. Поэтому в дальнейшем будет использоваться алгоритм для прямоугольных матриц.

Вышеприведенный алгоритм встроен в вычисление произведения (n, m)-Романи при <math>m = n^{\mu} \, </math> и <math>M = n^t \, </math> для некоторого t > 0, а время исполнения составляет <math>\tilde{O}(Mn^{\omega (1, \mu, 1)}) \, </math>. Следующий этап заключается во встраивании произведения (n, m)-Романи в алгоритм нахождения кратчайших путей между всеми парами. Первый алгоритм представляет собой последовательное применение операции возведения в квадрат, напоминающее второй этап алгоритма в [1]. Чтобы с пользой применить алгоритм произведения прямоугольных матриц (n, m)-Романи, нам потребуется определение мостового множества, которое будет играть ту же роль, что и множество I в алгоритме частичного вычисления матричного произведения в разделе «Постановка задачи».

Обозначим за <math>\delta(i,j) \, </math> кратчайшее расстояние между i и j, а за <math>n(i,j) \, </math> – минимальную длину среди всех кратчайших путей от i до j. Подмножество I множества вершин V является <math>\ell</math>-мостовым множеством, если удовлетворяет следующему условию: если <math>\eta(i,j) \ge \ell</math>, существует <math>k \in I</math>, такое, что <math>\delta(i,j) = \delta(i,k) + \delta(k,j) \, </math>. I является сильным <math>\ell</math>-мостовым множеством при выполнении условия: если <math>\eta(i,j) \ge \ell \, </math>, то существует <math>k \in I</math>, такое, что <math>\delta(i,j) = \delta(i,k) + \delta(k,j) \, </math> и <math>\eta(i,j) = \eta(i,k) + \eta(k,j) \, </math>. Заметим, что для графа с дугами единичной стоимости эти множества совпадают.

(2) Рассмотрим случай с единичными стоимостями дуг. В варианте (1) вычисление свидетелей производится дополнительно, то есть не является необходимым, если нужны только кратчайшие расстояния. Чтобы получить такую же сложность для точного, а не рандомизированного алгоритма, вычисление свидетелей становится обязательным. Как было отмечено ранее, поддержка свидетелей (то есть матрицы W) вносит дополнительный полилогарифмический коэффициент, что означает, что анализ может быть сосредоточен на произведении Романи в <math>\tilde{O} </math>-нотации. Более конкретно, I выбирается в качестве <math>\ell / 3</math>-мостового множества, являющегося сильным при единичной стоимости дуг. Чтобы вычислить I как <math>O(\ell)</math>-мостовое множество, необходимо получить вершины кратчайшего пути из i в j для каждого i и j, используя матрицу свидетелей W, за время <math>O(\ell)</math>. После получения этих <math>n^2 \,</math> множеств за время <math>O(\ell n^2)</math> можно вычислить <math>O(\ell)</math>-мостовое множество размера O(n ln n/ℓ) с той же временной сложностью, как показано в [10]. Процесс вычисления мостового множества должен остановиться в <math>\ell = n^{1/2} \, </math>, поскольку после этой границы процесс становится чрезмерно дорогим; в силу этого после данной границы используется одно и то же мостовое множество. Время вычисления до этой границы остается тем же, что и в варианте (1), а после границы составляет <math>\tilde{O}(n^{2.5}) \, </math>. Таким образом, мы получаем алгоритм из двух этапов.

(3) Если стоимости дуг положительны и ограничены <math>M = n^t > 0 \, </math>, сходная процедура может быть использована для вычисления <math>O(\ell)</math>-мостового множества размера O(n ln n/ℓ) за время <math>\tilde{O}(\ell n^2)</math>. Используя мостовое множество, задачу нахождения кратчайших путей между всеми парами вершин можно решить за время <math>\tilde{O}(n^{2 + \mu (t)}) \, </math> способом, сходным с вариантом (1). Этот результат можно обобщить на случай, когда стоимости дуг находятся в диапазоне от -M до M, сохранив ту же временную сложность, если модифицировать процедуру для вычисления <math>\ell</math>-мостового множества в случае, если не имеется отрицательных контуров. Подробности изложены в [10].

Среди оставшихся нерешенными задач особенно выделяются две. Первая заключается в уменьшении сложности <math>\tilde{O}(n^{2.575}) \, </math> при нахождении кратчайших путей между всеми парами вершин графа с дугами единичной стоимости. Вторая состоит в улучшении границы <math>M < O(n^{0.624}) \, </math> сложности алгоритма нахождения кратчайших путей между всеми парами вершин графа, стоимости дуг которого являются целыми числами не более M, и достижении значений ниже кубических.

* ''[[Алгоритм поиска кратчайших путей в разреженных графах]]'',