Есть ли более быстрые алгоритмы, чем Дейкстра?

Question

Для ориентированного связного графа только с положительными весами ребер, существуют ли более быстрые алгоритмы для поиска кратчайшего пути между двумя вершинами, чем Дейкстра с использованием кучи Фибоначчи?

Википедия говорит, что Дейкстра находится в O (| E | + | V | * log (| V |)) (используя кучу Фибоначчи).

Я не ищу оптимизацию, которая, например, вдвое меньше времени выполнения, а скорее алгоритмы, которые имеют разную сложность по времени (например, переход от O (n * log n) к O (n)).

Далее, я хотел бы узнать ваше мнение о следующем подходе:

1. Определить GCD всех весов ребер.
2. Преобразование графа в граф с равномерным весом ребер.
3. Используйте BFS, чтобы найти кратчайший путь между двумя заданными вершинами.

Пример для пункта 2:
Вообразите, что GCD равен 1. Тогда я бы преобразовал край
A ---> B (вес ребра 3)
в
A-> A '-> A' '-> B (3-кратный вес ребра 1)
Это преобразование стоит постоянного времени и должно быть сделано один раз для каждого края Поэтому я ожидаю, что этот алгоритм будет в O (| E |) (преобразование) + O (| E | + | V |) (BFS) = O (2 * | E | + | V |) = O (| E | + | V |)

Спасибо, что нашли время, чтобы прочитать мой вопрос, и я надеюсь не тратить ваше время ^^. Хорошего дня.

Answer 1

Большой анализ, который вы провели для своего алгоритма, глубоко ошибочен. Предположим, что все ребра являются простыми числами. Количество ребер в новом графе будет равно сумме всех весов. Таким образом, O(|E| + |V|) нового графа *1003* на самом деле O(W x |E| + |V|) в исходном графе, который может быть намного больше, чем O(|E| + |V| log |V|).

Answer 2

Есть ли более быстрые алгоритмы, чем Дейкстра?

Да. Вопрос не квалифицирован, чтобы требовать лучшей производительности во всех случаях, или даже в большинстве случаев. Для получения утвердительного ответа достаточно алгоритма с лучшей производительностью в одном случае.

Несмотря на, как правило, большее количество итераций, требуемых Метод Беллмана-Форда по методу Дейкстры, на практике метод Беллмана-Форда может быть превосходят из-за меньших издержек на одну итерацию [Голден Б., 1976. «Алгоритмы кратчайшего пути: сравнение», Operations Research, Vol. 44, стр. 1164-1168].

Цитата выше принадлежит Дмитрию П. Берцекасу (март 1992 г.). «Простой и быстрый алгоритм исправления меток для кратчайших путей» (PDF). Сети, вып. 23, стр. 703-709, 1993. http://www.mit.edu/people/dimitrib/SLF.pdf. Получено 2008-10-01.

Короче говоря, мое утверждение основано на интерпретации Берцекасом Голдена. Независимо от моего заключения, вы можете найти Берцекаса интересным для его классификации алгоритма Дейкстры как метод установки меток , в отличие от методов коррекции меток .

Answer 3

Существует алгоритм, который имеет O (1): превращать веса в длины цепей и использовать кольца ключей для узлов (реальные кольца ключей, как те, что в вашем кармане). Соедините кольца для ключей с правильными цепями. Выберите два узла и вытяните их друг от друга.

Следуйте за натянутыми цепями от одного узла к другому. Это самый короткий путь.

Чтобы реализовать это как компьютерную программу, вам понадобятся два промышленных робота:)

Для более реального примера используйте Оптимизация колонии муравьев , которая дает очень хорошие результаты за короткое время. Поскольку вы можете указать количество прогонов в этом алгоритме, вы можете решить, сколько времени он потратил (т. Е. Время выполнения зависит только от количества узлов), что дает вам O (n), но не гарантированный идеальный результат.

Answer 4

Всегда есть A *, и он происходит от иерархического A * и A * JPS.