В чем разница между «алгоритмом Флойда-Воршалла» и «Дейкстры Алгоритм», и что является лучшим для нахождения кратчайшего пути в графе?Лучший кратчайший путь алгоритм
мне нужно рассчитать кратчайший путь между всеми парами в сети и сохранить результаты в массив следующим образом:
**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 алгоритм находит самый короткий путь между узлом и каждым другим узлом на графике. Вы будете запускать его один раз для каждого узла. Весы должны быть неотрицательными, поэтому при необходимости вам сначала необходимо нормализовать значения в графике.
Floyd-Warshall рассчитывает кратчайшие маршруты между всеми парами узлов за один проход! Вес цикла должен быть неотрицательным, а график должен быть направленный (ваша диаграмма отсутствует).
Алгоритм Алжира использует алгоритм Дейкстры, чтобы найти все пары за один проход и быстрее для редких деревьев (см. Ссылку для анализа).
Из ссылки wikipedia, которую вы цитируете для Dijkstra: «Алгоритм находит путь с наименьшей стоимостью между этой вершиной и ** каждой ** другой вершиной» (мой акцент). Таким образом, вам не нужно запускать его для каждой пары вершин, но только для каждой вершины. –
thx Andreas, fixed – Will
Вы можете преобразовать неориентированный граф в ориентированный граф, заменив каждое ребро uv двумя ребрами (u, v) и (v, u) с тем же весом. Тогда, предположительно, Флойд-Варшалл должен отлично работать? –
Floyd Воршалл найти пути между всеми парами вершин, но Дейкстр только находит путь от одной вершины ко всем остальным.
Floyd Воршалл является O (| V |) и Dikstra является O (| E | + | V | войти | V |), но вы должны запустить его V раза, чтобы найти все пары, которые дают сложность O (| E * V | + | V | log | V |) Я думаю. Это означает, что, возможно, быстрее использовать Dijsktra многократно, чем алгоритм FW, я бы попробовал оба подхода и посмотрел, какой из них наиболее быстрый в реальном случае.
Комментарий Фрэнсиса Хаарта: «@ Андреас Бринк, на полном графике, E = (V^2-V)/2, а dijkstra не будет быстрее». –
Используйте алгоритм Флойда-Варшалла, если вы хотите найти кратчайший путь между всеми парами вершин, так как он имеет (дальнее) более высокое время работы, чем алгоритм Дейкстры.
Алгоритм Флойда-Воршалла имеет худший показатель случае O (| V |), где, как Дейкстры имеет худшую производительность случае O (| E | + | V | войти | V |)
Dijkstra находит самый короткий путь только один vertex, Floyd-Warshall находит его между все из них.
Dijkstra's в основном предназначен для определения кратчайшего пути для одной пары, от одного узла до всех других узлов, где, поскольку Floyd-Warshall предназначен для кратчайшего пути всех пар, т.е. самого короткого пути между всеми парами вершин. Алгоритм Флойда-Варшалла имеет наихудшую производительность O (| V | 3), где, поскольку Dijkstra имеет худшую производительность O (| E | + | V | log | V |) Также Dijkstra не может использоваться для отрицательных (мы используем для этого Bellmann Ford). но для Floyd-Warshall мы можем использовать отрицательные веса, но не отрицательные циклы
В то же время известны лучшие алгоритмы для кратчайшего пути с одним источником. Практически актуальным является derivation of Dijkstra's algorithm by Torben Hagerup. Алгоритм имеет такую же худшую сложность, как и Djikstra, но в среднем случае ожидаемая продолжительность выполнения линейна по размеру графика, что намного быстрее, чем чистый Dijkstra. Идея алгоритма основана на идее, что нет необходимости всегда опросить минимальный фронт из очереди.Можно опросить край от очереди, вес которого 1+k раз больше минимального веса кромки, где k - это некоторое число больше 0. Даже если такое ребро выбрано, алгоритм все равно найдет кратчайший путь.
, но другой был закрыт, главным образом из-за плохого английского пользователя, и одно из решений назвало эти точные два алгоритма альтернативами. Если мы закроем это как дуп, как автор узнает больше о предыдущем вопросе? Неужели мы действительно будем достаточно хороши, чтобы пойти туда и проголосовать за повторное открытие? – Will
привет, но хотел добавить пример массива относительно изображения, но я не делал – ricardo
спасибо, SilentGhost для повторного редактирования моего вопроса – ricardo