Я реализовал решение алгоритма Беллмана-Форда с очередью и сравнил его производительность с алгоритмом Дейкстры. Они были довольно близки, и это было для меня неожиданностью, потому что сложность Беллмана-Форда равна O(NM). Знаю, что сложность на самый худой случай, но все равно результат удивил. Я искал некоторую информацию о Беллмане-Форде и нашел только это утверждение в Sedgewick, Algorithms in Java: «в реальных сетях алгоритм Беллмана-Форда обычно работает за линейное время». Не могли бы вы дать мне объяснение производительности алгоритма Беллмана-Форда?
Производительность алгоритма кратчайшего пути Беллмана – Форда
comment
Если вы ищете хорошие реализации обоих алгоритмов в С++, см. Boosts Graph lib. boost.org/doc/libs/1_39_0/libs/ график/doc/table_of_contents.html
- person RED SOFT ADAIR schedule 16.06.2009
comment
Код находится здесь: github.com/boostorg/graph/ блоб/разработать/включить/повысить/график/
- person assylias schedule 24.08.2018
Ответы (1)
Вот довольно прямолинейная статья об этом (Ссылка на PDF).
Сложность алгоритма Беллмана-Форда зависит от количества проверок границ или вызовов релаксации. (Обратите внимание, что это отличается от шагов релаксации, которые относятся к фактически выполненным изменениям.) Как уже упоминалось, количество вызовов релаксации может быть меньше, чем |V ||E| с реализацией BGL. На самом деле она намного меньше, чем |V ||E| в среднем случае.
В нем также перечислены псевдокоды и дальнейший анализ.
person
JP Alioto
schedule
15.06.2009
