Performance of Bellman–Ford shortest path algorithm

Question

I implemented the solution of Bellman - Ford algorithm with a queue and I compared its performance with the Dijkstra algorithm. They were pretty close and that was a surprise for me because the complexity of Bellman - Ford is O(NM). I know that the complexity is for the worst case, but still the result was surprising. I searched for some information about Bellman - Ford and I found only this statement in Sedgewick, Algorithms in Java "on real networks the Bellman–Ford algorithm typically runs in linear time". Could you give me an explanation of the Bellman - Ford algorithm performance behaviour?

Answer 1

Here's a paper on it that's pretty straight forward (PDF Link).

The complexity of the Bellman-Ford algorithm depends on the number of edge examinations, or relaxation calls. (Note this is different from relaxation steps which refer to the actual changes performed.) As mentioned, the number of relaxation calls can be smaller than |V ||E| with the BGL implementation. In fact, it is much smaller than |V ||E| in the average case.

It lists pseudocode and further analysis as well.