title: Performance of Bellman–Ford shortest path algorithm
body: <p>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?</p>