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

Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 47: Строка 47:
Первый этап заменяется алгоритмом на основе произведения (n, n)-Романи, а второй этап модифицируется таким образом, чтобы иметь дело с длинами путей, а не расстояниями.
Первый этап заменяется алгоритмом на основе произведения (n, n)-Романи, а второй этап модифицируется таким образом, чтобы иметь дело с длинами путей, а не расстояниями.


Заметим, что граница M была заменена на ℓM в произведении матриц расстояния на первом этапе. Игнорируя полилогарифмические коэффициенты, получаем время исполнения для первого этапа – Õ(nr2М). Мы предполагаем, что M соответствует O(nk) для некоторого константного k. Сравнивая эту сложность со сложностью второго этапа, O(n3/r), получаем полное время вычисления Õ(n(6+)/3М1/3) при выборе r = О{n(3-)/3M-1/3). Чтобы время исполнения оказывалось меньше кубического, значение M должно почти совпадать с O(n0.624).
Заметим, что граница 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>.
 
 
== Основные результаты ==


Основные результаты
Цвик улучшил алгоритм Алона-Галила-Маргалита в нескольких отношениях. Самым серьезным улучшением стало снижение времени нахождения кратчайших путей между всеми парами с O(n2.688) до O(n2.575) для дуг единичной стоимости. Наибольшее ускорение в алгоритме Алона-Галила-Маргалита [1] было достигнуто в быстрой операции булева произведения матриц, а в алгоритме Такаоки [9] – в быстром умножении матриц расстояния по Романи; в обоих случаях мы имели дело с быстрым матричным умножением квадратных матриц.
Цвик улучшил алгоритм Алона-Галила-Маргалита в нескольких отношениях. Самым серьезным улучшением стало снижение времени нахождения кратчайших путей между всеми парами с O(n2.688) до O(n2.575) для дуг единичной стоимости. Наибольшее ускорение в алгоритме Алона-Галила-Маргалита [1] было достигнуто в быстрой операции булева произведения матриц, а в алгоритме Такаоки [9] – в быстром умножении матриц расстояния по Романи; в обоих случаях мы имели дело с быстрым матричным умножением квадратных матриц.
   
   
Источник — http://pco.iis.nsk.su/wega/index.php/Алгоритм_поиска_кратчайших_путей_между_всеми_парами_при_помощи_матричного_произведения