Motivation

Bellman-Ford repose sur une seule opération, relaxation : pour une arête u -> v de poids w, si passer par u est moins coûteux (dist[u] + w < dist[v]), mettez à jour dist[v]. Faites cela pour chaque arête, de manière répétée.

Pourquoi apprendre Bellman-Ford ?

• Poids négatifs : il fonctionne là où Dijkstra échoue, par exemple pour des coûts qui peuvent être des remises ou de l'arbitrage de devises.
• Détection de cycles négatifs : une passe de relaxation supplémentaire révèle les cycles dont le poids total est négatif.
• Simplicité : pas de file de priorité, juste une relaxation d'arêtes répétée.

Le compromis est la vitesse : O(V * E), plus lent que le O((V + E) log V) de Dijkstra.