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

Question

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

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

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

Answer 1

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

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

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

Короче:

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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