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

Алгоритм Беллмана-Форда решает задачу нахождения кратчайшего пути с единственным источником за время 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]).

Наиболее современные исследования проблемы кратчайших путей предполагают, что длины дуг являются целыми числами в диапазоне {–C, ..., C} либо {0, ..., C}. Одно из направлений сводит поиск кратчайшего пути между всеми парами к серии стандартных операций матричного умножения. Применимость этих алгоритмов ограничена, поскольку время выполнения линейно растет пропорционально C. Существуют более быстрые алгоритмы для поиска кратчайшего пути с единственным источником как для неотрицательных длин дуг, так и для произвольных длин дуг. Первые задействуют мощь оперативной памяти, проводя сортировку за время o(n log n); вторые основываются на технике [[масштабирование|масштабирования]]. Цвик [19] приводит обзор алгоритмов нахождения кратчайших путей вплоть до 2001 года.

Алгоритм Петти для поиска кратчайших путей между всеми парами [13] адаптирует [[иерархия|иерархический подход]] Торупа [17] (разработанный для неориентированных графов с целочисленными весами) для ориентированных графов с действительными весами. Теорема 1 описывает первое улучшение времени выполнения по сравнению с <math>O(mn + n^2 log n)</math> алгоритма Дейкстры для произвольных графов с действительными весами.

Этот алгоритм достигает логарифмического ускорения благодаря применению трех новых техник. Первая заключается в использовании неизбежного сходства между кратчайшими путями с единственным источником, исходящими из расположенных неподалеку вершин. Вторая представляет собой метод вычисления дискретных приближенных расстояний в графах с действительными весами. Третьей техникой является новый алгоритм иерархического типа для нахождения кратчайших путей с единственным источником, который при наличии приближенных расстояний достаточной точности выполняется за время O(m + n log log n).

Второй результат исследований [13, 15] гласит, что не существует алгоритма иерархического типа для поиска кратчайших путей, время выполнения которого было бы лучше, чем O(m + n log n)алгоритма Дейкстры.

'''Проблема 2'''. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных графов с неотрицательными весами с временем выполнения O(m) + o(n log n)? Существует ли он для неориентированных графов?

'''Проблема 4'''. Существует ли алгоритм поиска кратчайших путей между всеми парами со сложностью ниже кубической, т.е. меньше <math>O(n^{3 - \epsilon}) \, </math>?Существует ли алгоритм поиска кратчайших путей между всеми парами со сложностью ниже кубической для графов с целочисленными весами со слабой зависимостью от наибольшего веса дуги C, т. е. выполняющийся за время <math>O(n^{3 - \epsilon} polylog(C)) \, </math>?