Performance de l'algorithme du plus court chemin de Bellman-Ford

Question

J'ai implémenté la solution de l'algorithme de Bellman-Ford avec une file d'attente et j'ai comparé ses performances avec l'algorithme de Dijkstra. Ils étaient assez proches et cela a été une surprise pour moi car la complexité de Bellman - Ford est O (NM). Je sais que la complexité est dans le pire des cas, mais le résultat était quand même surprenant. J'ai cherché quelques informations sur Bellman - Ford et je n'ai trouvé que cette déclaration dans Sedgewick, Algorithms in Java "sur de vrais réseaux l'algorithme de Bellman-Ford fonctionne typiquement en temps linéaire". Pourriez-vous me donner une explication du comportement de performance de l'algorithme de Bellman-Ford?

Answer 1

Voici un papier sur ce qui est assez simple (PDF Link).

La complexité de l'algorithme Bellman-Ford dépend du nombre de examens de bord, ou des appels de relaxation. (Notez que ceci est différent de étapes de relaxation qui se réfèrent aux changements réels effectués.) Comme mentionné, le nombre d'appels de relaxation peut être inférieur à | V || E | avec l'implémentation BGL. En fait, il est beaucoup plus petit que | V || E | dans le cas moyen .

Il répertorie également le pseudocode et d'autres analyses.