Выполнение алгоритма кратчайшего пути Bellman-Ford

Question

Я реализовал алгоритм Bellman-Ford с очередью, и я сравнил его производительность с алгоритмом Дейкстры. Они были довольно близки, и это было для меня неожиданностью, потому что сложность Bellman-Ford - O (NM). Я знаю, что сложность в худшем случае, но результат был неожиданным. Я искал некоторую информацию о Bellman-Ford, и я нашел только это утверждение в Sedgewick, Algorithms in Java. «В реальных сетях алгоритм Bellman-Ford обычно работает в линейном времени». Не могли бы вы дать мне объяснение поведения производительности Bellman-Ford?

Answer 1

Вот бумага, которая довольно проста (PDF Link).

Сложность алгоритма Беллмана-Форда зависит от количества краевых экзаменов, или вызовы релаксации. (Обратите внимание, что это отличается от шагов релаксации, которые относятся к действительным выполненным изменениям .) Как уже упоминалось, количество обращений может быть меньше, чем | V || E | с реализация BGL. Фактически, это намного меньше, чем | V || E | в среднем .

В нем перечислены псевдокоды и дальнейший анализ.