Desempenho do algoritmo Bellman -Fford Sortest Path

Question

Implementei a solução do algoritmo Bellman - Ford com uma fila e comparei seu desempenho com o algoritmo Dijkstra. Eles estavam bem próximos e isso foi uma surpresa para mim porque a complexidade de Bellman - Ford é O (NM). Eu sei que a complexidade é para o pior caso, mas ainda assim o resultado foi surpreendente. Eu procurei algumas informações sobre Bellman - Ford e encontrei apenas essa afirmação em Sedgewick, algoritmos em Java "nas redes reais, o algoritmo Bellman -Fford normalmente roda em tempo linear". Você poderia me dar uma explicação do comportamento de desempenho do algoritmo Bellman - Ford?

Answer 1

Aqui está um artigo que é bem direto (Link pdf).

A complexidade do algoritmo de Bellman-Ford depende do número de exames de borda ou chamadas de relaxamento. (Observe que isso é diferente das etapas de relaxamento que se referem às mudanças reais realizadas.) Como mencionado, o número de chamadas de relaxamento pode ser menor que | v || e | com a implementação do BGL. De fato, é muito menor que | v || e | no caso médio.

Ele lista também pseudocódigo e análises adicionais.