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

Заметим, что граница 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>.

== Основные результаты ==

   

В данном разделе «ускорителем» служит алгоритм быстрого умножения матриц расстояния по Романи, созданный на основе алгоритма быстрого умножения прямоугольных матриц, разработанного Копперсмитом [4] и Хуангом и Пэном [5]. Пусть (p, q, r) – порядок временной сложности при умножении матриц (np, nq) и (nq, nr). Предположим, что произведение матриц (n, m) и (m, n) может быть вычислено за О(n((1,,1)) арифметических операций, где m = n и 0 ≤  ≤ 1. Нам известно следующее: O(n(1,1,1)) = O(n2.376) и O(n(1,0.294,1)) = Õ(n2). Для вычисления произведения квадратных матриц (n, n) требуется n1- операций матричного умножения, что дает время исполнения О(n((1,,1)+1-), которое можно преобразовать в O(n2+), где  удовлетворяет равенству (l,,1) = 2 + 1. На данный момент лучшее известное значение  составляет  = 0.575, так что временная граница превращается в O(n2.575) – это значение уступает O(n2.376). Поэтому в дальнейшем будет использоваться алгоритм для прямоугольных матриц.