Производительность алгоритма Беллмана – Форда по кратчайшему пути

Question

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

Answer 1

Вот документ, который довольно прост ( PDF Link ).

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

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