В чем разница между алгоритмом "Флойд-Варшалл" и "Dijkstra Algorithm" и который лучше всего подходит для поиска кратчайшего пути в графе?
Мне нужно рассчитать кратчайший путь между всеми парами в сети и сохранить результаты в массиве следующим образом:
**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
Dijkstra алгоритм находит кратчайший путь между node и любым другим node на графике. Вы запускаете его один раз для каждого node. Весы должны быть неотрицательными, поэтому при необходимости вам необходимо сначала нормализовать значения в графе.
Floyd-Warshall вычисляет кратчайшие маршруты между всеми парами узлов за один проход! Весы цикла должны быть неотрицательными, а график должен быть направлен (ваша диаграмма отсутствует).
Johnson алгоритм использует алгоритм Дейкстры для поиска всех пар за один проход и быстрее для редких деревьев (см. ссылку для анализ).
Флойд Варшалл находит пути между всеми парами вершин, но Дийкстра только находит путь от одной вершины ко всем остальным.
Floyd Warshall - это O (| V | 3), а Дикстра - O (| E | + | V | log | V |), но вам нужно будет запустить его в V раз, чтобы найти все пар, что дает сложность O (| E * V | + | V 2 | log | V |) Я предполагаю. Это означает, что, возможно, быстрее использовать Dijsktra многократно, чем алгоритм FW, я бы попробовал оба подхода и посмотрел, какой из них наиболее быстр в реальном случае.
Используйте алгоритм Floyd-Warshall, если вы хотите найти кратчайший путь между парами вершин all, так как он имеет (гораздо большее) время работы, чем алгоритм Дейкстры.
Алгоритм Флойда-Варшалла имеет наихудшую производительность O (| V | 3), где, поскольку Dijkstra имеет худшую производительность O (| E | + | V | log | V |)
Dijkstra находит кратчайший путь только из одной вершины, Floyd-Warshall находит его между всеми из них.
Dijkstra - это, в основном, для нахождения кратчайшего пути для одной пары, т.е. от одного node ко всем другим узлам, где, поскольку Floyd-Warshall предназначен для кратчайшего пути всех пар, т.е. самого короткого пути между всеми парами вершин. Алгоритм Флойда-Варшалла имеет наихудшую производительность O (| V | 3), где, поскольку Dijkstra имеет худшую производительность O (| E | + | V | log | V |), Также Dijkstra нельзя использовать для отрицательных весов (мы используем Bellmann Ford для этого же). но для Флойда-Варшалла мы можем использовать отрицательные веса, но отрицательных циклов
В то же время известны более эффективные алгоритмы для проблемы с самым коротким единственным источником. Практически актуальным является вывод алгоритма Дейкстры Torben Hagerup. Алгоритм имеет такую же худшую сложность, как и Djikstra, но в среднем случае ожидаемая продолжительность выполнения линейна по размеру графика, что намного быстрее, чем чистый Dijkstra. Идея алгоритма основана на идее, что нет необходимости всегда опросить минимальный фронт из очереди. Можно опросить край из очереди, вес которой 1+k раз больше минимального веса края, где k - это число больше 0. Даже если такое ребро выбрано, алгоритм все равно найдет кратчайший путь.