Лучший алгоритм кратчайшего пути

Question

В чем разница между "алгоритмом Флойда-Варшалла" и "Алгоритмом Дейкстры" , и который является лучшим для поиска кратчайшего пути в графе?

Мне нужно рассчитать кратчайший путь между всеми парами в сети и сохранить результаты в массив следующим образом:

**A     B     C     D      E**
A 0     10    15    5     20
B 10     0    5     5     10
C 15     5    0     10    15
D 5      5    10    0     15
E 20     10    15   15    0

Answer 1

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

Флойд-Варшалл рассчитывает кратчайшие маршруты между всеми парами узлов за один проход! Вес цикла должен быть неотрицательным, а график должен быть направленным (ваша диаграмма - нет).

Алгоритм Джонсона использует алгоритм Дейкстры для поиска всех пар за один проход и быстрее для разреженных деревьев (см. Ссылку для анализа).

Answer 2

Флойд Варшалл находит пути между всеми парами вершин, но Дейкстра находит путь только от одной вершины ко всем остальным.

Флойд Варшалл - O (| V | ³ ), а Дикстра - O (| E | + | V | log | V |), но вам придется запустить его V раз, чтобы найти все пары который дает сложность O (| E * V | + | V ² | log | V |) Я думаю. Это означает, что, возможно, быстрее использовать Dijsktra несколько раз, чем алгоритм FW, я бы попробовал оба подхода и выяснил, какой из них наиболее быстрый в данном случае.

Answer 3

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

Answer 4

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

Алгоритм Флойд-Варшалла имеет худшую производительность O (| V | ³ ), где, как у Дейкстры, производительность O худшая: (E + + V | log | V | )

Answer 5

Между тем известны лучшие алгоритмы для задачи кратчайшего пути из одного источника. Практически актуальным является вывод алгоритма Дейкстры от Торбена Хагерупа . Алгоритм имеет ту же сложность в худшем случае, что и Джикстра, но в среднем ожидаемое время выполнения линейно по размеру графа, что намного быстрее, чем у чистого Дейкстры. Идея алгоритма основана на идее, что нет необходимости всегда опрашивать минимальное ребро из очереди. Можно опросить ребро из очереди, вес которого в 1+k раза больше минимального веса ребра, где k - это некоторое число, большее 0. Даже если выбрано такое ребро, алгоритм все равно найдет кратчайший путь.

Answer 6

Дейкстры в основном предназначены для нахождения кратчайшего пути в одной паре, то есть от одного узла ко всем остальным узлам, тогда как Флойд-Варшалл для кратчайшего пути для всех пар, т.е. Алгоритм Флойда-Варшалла имеет худшую производительность O (| V | 3), где, как у Дейкстры, худшая производительность O (| E | + | V | log | V |) Также Дейкстры нельзя использовать для отрицательных весов (мы используем Беллмана Форда для того же самого). но для Флойд-Варшалла мы можем использовать отрицательные веса, но без отрицательных циклов