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

В любом из трех случаев матрица 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)) путем последовательного применения метода возведения в квадрат, заключающегося в повторном выполнении D ← D × D O(log n) раз.