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

Алгоритм Беллмана-Форда решает задачу нахождения кратчайшего пути с единственным источником за время O(mn) в предположении, что длины дуг неотрицательны; алгоритм Дейкстры решает ее за время O(m + nlog n). Существует широко известное преобразование с сохранением кратчайших путей и временем выполнения O(mn), заменяющее любую функцию длины на неотрицательную функцию длины. Используя это преобразование и n проходов алгоритма Дейкстры, получаем алгоритм нахождения кратчайшего пути между всеми парами с временем выполнения <math>O(mn + n^2 log n) = O(n^3)</math>. Алгоритм Флойда-Уоршелла вычисляет кратчайший путь между всеми парами более прямолинейным способом и за время <math>O(n^3)</math>. Описание этих алгоритмов можно найти в [4]. Известно, что поиск кратчайшего пути между всеми парами является асимптотически эквивалентным матричному умножению (min; +) [1], которое поддается вычислению при помощи неравномерного алгоритма, выполняющего <math>O(n^{2.5})</math> числовых операций [6]. (Наиболее быстрый известный матричный умножитель (min; +) выполняется за время <math>O(n^3(log log n)^3/(log n)^2)</math> [3]).