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

В любом из трех случаев матрица C называется произведением, а процесс вычисления – умножением. Во всех трех случаях k пробегает весь диапазон (1, ..., n}. Частичное произведение матриц A и В определяется для значений k из подмножества I множества V. Иными словами, частичное произведение получается при умножении вертикальной прямоугольной матрицы A(*, I), столбцы которой извлечены из матрицы A согласно множеству I, и горизонтальной прямоугольной матрицы B(I, *), полученной из B путем извлечения строк, соответствующих множеству I. Интуитивно множество I представляет собой множество контрольных точек k при переходе от i к j в графе.

Лучший алгоритм [3] вычисляет произведение (1) за время <math>O(n^ \omega) \, </math>, где <math>\omega \, </math> = 2.376. Далее мы будем учитывать три знака после запятой. Для вычисления произведения (2) булевы значения 0 и 1 в матрицах A и B можно рассматривать как целые числа, применить алгоритм для вычисления (1) и затем заменить ненулевые элементы получившейся матрицы на 1. Следовательно, его сложность также равна <math>O(n^ \omega) \, </math>. ''Свидетели'' произведения (2) задаются матрицей свидетелей <math>W = {w_{ij}} \, </math>, где <math>w_{ij} = k \, </math> для некоторого k, такого, что <math>a_{ik} \wedge b_{kj} = 1</math>. Если такого k не существует, <math>w_{ij} = 0 \, </math>. ''Матрица свидетелей'' <math>W = w_{ij} \, </math> для (3) определяется следующим образом: <math>w_{ij} = k \, </math>, при котором значение <math>c_{ij} \,</math>  минимально. Если существует алгоритм для (3) с временем T(n), игнорирующий полилогарифмический коэффициент n, задача поиска кратчайших путей между всеми парами может быть решена за время Õ(T(n)) путем последовательного применения метода возведения в квадрат, заключающегося в повторном выполнении <math>D \leftarrow D \times D</math> <math>O(\log n) \,</math> раз.

Полное изложение алгоритма приведено в [1]. Пусть все дуги графа имеют единичную стоимость. Пусть D(ℓ) – ℓ-я приближенная матрица для D*, определенная следующим образом: d(ℓ)ij = d*ij, если d*ij ≤ ℓ, и d(ℓ)ij =  в противном случае. Пусть A – матрица смежности графа G: aij = 1, если существует дуга (i, j), и aij = 0 в противном случае. Пусть aii = 1 для всех i. Алгоритм состоит из двух этапов. На первом этапе вычисляются D(ℓ) для ℓ= 1, …, r при помощи проверки (i, j)-го элемента Aℓ = {aℓij}. Заметим, что если aℓ = 1, то существует путь из i в j длиной ℓ или меньше. Поскольку булево произведение матриц может быть вычислено за время O(n), время выполнения этого этапа составит O(rn).

На втором этапе алгоритм вычисляет D(ℓ) для ℓ = r, 3/2 r, 3/2 3/2 r, ... , n’ путем последовательного возведения в квадрат, где n’ – наименьшее целое число в последовательности ℓ, такое, что ℓ  n. Пусть Tiα = {j  d(ℓ)ij = α} и Ii = Tiα, такое, что Tja минимально для ℓ/2 < α < ℓ. Основное наблюдение второго этапа заключается в следующем: необходимо проверять k только в Ii, размер которого не превышает 2n/ℓ, поскольку корректные расстояния между ℓ + 1 и 3ℓ/2 могут быть получены как суммы d(ℓ)ik + d(ℓ)kj для некоторых k, удовлетворяющих неравенству ℓ/2 ≤ d(ℓ)ik ≤ ℓ. Значение Ii сходно с I для частичных произведений – за тем исключением, что I меняется для каждого i. Таким образом, время одного возведения в квадрат составляет O(n3/ℓ); а полное время второго этапа задается при N = log3/2 n/r формулой  . Сбалансировав оба этапа условием rn = n3/r, получаем время O(n(+3)/2) = O(n2.688) для алгоритма с r = О(n(3-)/2).