Есть ли случай, когда повторение Беллмана-Форда лучше, чем Флойд-Варшалл?

Question

Учитывая тот факт, что повторяющийся Беллман-Форд имеет временную сложность O (V (^ 2) * E) и Флойд-Варшалла O (V ^ 3), в этом случае лучше использовать повторяющийся Беллман-Форд дляполучить минимальные пути всех пар?В каком случае это хуже?

Answer 1

Внедренная реализация Bellman Ford требует времени O (V * E) для каждого прогона.Он может победить Флойда Варшалла только тогда, когда E

Однако есть оптимизация, которую вы можете сделать.Вариант Bellman Ford, который использует очередь, аналогично тому, как работает BFS, за исключением того, что элемент может добавляться в очередь несколько раз, когда достигается лучшая стоимость.На практике, на случайно сгенерированных графах это имеет тенденцию работать почти так же хорошо, как Дейкстра с кучами, что составляет O (E log V).

Answer 2

Как вы уже знаете сложность (повторяющиеся Bellman-ford = O((V^2)*E) и Floyd-warshall O(V^3)), вы можете легко проанализировать, что будет лучше для вашего графика.Если E < V использовать Bellmam-ford, в противном случае используйте Floys-warshall.

Основное применение для Bellman ford - найти отрицательный цикл на графике.Для Флойд Уорсхолл это найти все пары кратчайшего пути.

Обычно в графе число ребер (E) всегда больше, чем вершин (V).Итак, я предлагаю использовать Floyd-warshall .

Если у вашего графа есть возможность иметь отрицательный цикл, тогда вы должны использовать Bellman ford, чтобы проверить, имеет ли граф отрицательный цикл.