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

Заметим также, что если <math>(2/3) \ell \le \mu(i,j) \le \ell \,</math> и I является сильным <math>\ell/3</math>-мостовым множеством, существует <math>k \in I</math>, такое, что <math>\delta(i,j) = \delta(i,k) + \delta(k,j) \, </math> и <math>\mu(i,j) = \mu(i, k) + \mu(k,j) \,</math>. Если выполняется свойство сильного мостового множества, произведение (n, m)-Романи может быть использовано для решения задачи нахождения кратчайших путей между всеми парами следующим образом. Последовательным применением возведения в квадрат, как в случае алгоритма Алона-Галила-Маргалита, алгоритм вычисляет <math>D^{(\ell)} \, </math> для <math>\ell = 1, \mathcal{d} 3/2 \mathcal{e}, \mathcal{d} 3/2 \mathcal{d} 3/2 \mathcal{e} \mathcal{e}, ... , n' \, </math> (где n' – первое значение <math>\ell</math>, превышающее n), используя различные варианты множества I, описанного ниже. Для вычисления мостового множества алгоритм поддерживает матрицу свидетелей с дополнительным полилогарифмическим коэффициентом в оценке сложности. В источнике [10] предложены три способа выбора множества I. Пусть <math>|I| = n^r \, </math> для некоторого r, <math>0 \le r \le 1</math>.

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

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