Дикстра против Флойда-Варшалла: поиск оптимального маршрута на всех парах node

Я читаю алгоритм Дейкстры и алгоритм Флойда-Варшалла. Я понимаю, что Dijkstra находит оптимальный маршрут от одного node ко всем другим узлам, а Floyd-Warshall находит оптимальный маршрут для всех спариваний node.

Мой вопрос в том, будет ли алгоритм Дейкстры более эффективным, чем Floyd, если я запустил его на каждом node, чтобы найти оптимальный маршрут между всеми спариваниями.

Время работы Dijkstra равно O (E + VlogV), где Floyd - O (V ³). Если Dijkstra терпит неудачу, каково будет его время выполнения в этом случае? Спасибо!

Ответ 1

Как отмечали другие, Floyd-Warshall работает во времени O (n ³) и запускает поиск Dijkstra из каждого node друг другу node, предполагая, что вы используете Куча Фибоначчи, чтобы поддержать реализацию Dijkstra, принимает O (mn + n ² log n). Однако вы не всегда можете безопасно запускать Dijkstra на произвольном графе, потому что алгоритм Дейкстры не работает с отрицательными весами ребер.

Существует поистине замечательный алгоритм, называемый алгоритм Джонсона, который представляет собой небольшую модификацию для запуска алгоритма Дейкстры из каждого node, который позволяет этому подходу работать, даже если граф содержит отрицательные ребра (пока нет отрицательных циклов). Алгоритм работает, сначала используя Bellman-Ford на графике, чтобы преобразовать его в график без отрицательных ребер, затем используя алгоритм Дейкстры, начиная с каждой вершины, Поскольку Bellman-Ford работает во времени O (mn), общая асимптотическая среда выполнения все еще O (mn + n ² log n), поэтому, если m = o (n ²) (заметим, что это мало-о n), этот подход асимптотически быстрее, чем использование Флойда-Варшалла.

Единственный улов в том, что это предполагает, что у вас есть алгоритм Дейкстры, поддерживаемый кучей Фибоначчи. Если у вас нет доступной кучи Fibonacci и вы не хотите вставлять 72 часа, необходимые для сборки, отладки и тестирования, тогда вы все равно можете использовать двоичную кучу для алгоритма Дейкстры; он просто увеличивает время выполнения до O (m log n), поэтому эта версия алгоритма Джонсона работает в O (mn log n). Это уже не всегда асимптотически быстрее, чем Floyd-Warshall, потому что если m = & Omega; (n ²), то Floyd-Warshall работает в O (n ³), а алгоритм Джонсона выполняется в O (n ³ log n). Однако для разреженных графов, где m = o (n ²/log n), эта реализация алгоритма Джонсона по-прежнему асимптотически лучше, чем Floyd-Warshall

Короче:

С кучей Фибоначчи алгоритм Джонсона всегда асимптотически, по крайней мере, так же хорош, как и Флойд-Варшалл, хотя сложнее кодировать код.
С бинарной кучей алгоритм Джонсона обычно асимптотически, по крайней мере, так же хорош, как и Floyd-Warshall, но не является хорошим вариантом при работе с большими плотными графами.

Надеюсь, это поможет!

Ответ 2

Сложность запуска Dijkstra на всех узлах будет O (EV + V ² logV). Эта сложность ниже O (V ³), если E < В ².

Ответ 3

Это зависит. Запуск Dijkstra для всех узлов дает вам O(VE + V^2log V), а Floyd - O(V^3). Если E = O(V^2), то они теоретически идентичны, а Флойд быстрее на практике. Если вы E = O(V), то запустите Dijkstra для всех узлов, если лучше, как в теории, так и на практике.

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

Ответ 4

Нет практически Флойд-Варшалл быстрее, чем Дейкстра для всего кратчайшего пути пары (обычно!!)