Running Bellman-Ford Shortest Path Algorithm

Question

I implemented a Bellman-Ford algorithm solution with a queue, and I compared its performance with Dijkstra's algorithm. They were pretty close, and it was a surprise to me because the complexity of Bellman-Ford is O (NM). I know that complexity is the worst case scenario, but the result was unexpected. I was looking for some information about Bellman-Ford, and I only found 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 performance behavior of the Bellman-Ford algorithm?

Answer 1

Here is a document on it that is pretty straight forward ( PDF Link ).

The complexity of the Bellman-Ford algorithm depends on the number of regional exams or relaxation calls. (Please note that this is different from relaxation steps that relate to actual changes made.) As already mentioned, the amount of relaxation calls may be less than | V || E | with implementation of BGL. In fact, it is much less | V || E | in the middle case.

It also lists pseudo-code and further analysis.