44. Gérer les Poids Négatifs : Introduction à Bellman-Ford

L'algorithme de Dijkstra échoue s'il y a des poids d'arête négatifs, car son hypothèse gloutonne (que la distance minimale trouvée jusqu'à présent est définitive) peut être invalidée par un chemin ultérieur qui inclut une arête négative.

L'Algorithme de Bellman-Ford

Bellman-Ford résout le problème du plus court chemin à source unique même dans les graphes avec des poids négatifs.

Concept de Base : Relaxation Itérative

Au lieu de fixer gloutonnement les chemins, Bellman-Ford relaxe (met à jour) itérativement toutes les arêtes du graphe V-1 fois (où V est le nombre de sommets).

1. Initialiser les distances (source=0, autres=infini).
2. Répéter V-1 fois :
   • Pour chaque arête (U, V) dans le graphe :
     • Si dist[U] + weight(U, V) < dist[V], mettre à jour dist[V].

Détection de Cycles Négatifs

Si nous exécutons l'étape de relaxation une V-ième fois et constatons que nous pouvons toujours relaxer (mettre à jour) une distance, cela signifie qu'un cycle négatif existe. Les chemins les plus courts ne sont pas définis dans les graphes accessibles à partir d'un cycle négatif.