Une remise, une compensation ou une variation de valeur peut produire un coût négatif. Dijkstra ne dispose alors plus de sa garantie habituelle. Bellman-Ford accepte ces poids en améliorant les distances par passages successifs sur les arcs. Il permet aussi de reconnaître une situation plus grave : un cycle que l'on pourrait répéter pour réduire le coût sans limite.
Un poids négatif n'implique pas automatiquement un cycle négatif. Un réseau orienté peut contenir une remise sur une transition sans permettre de revenir à son point de départ. Dans ce cas, un minimum fini peut parfaitement exister. Il faut distinguer une propriété locale, le signe d'un arc, d'une propriété globale, le coût d'un circuit.
En non orienté, une arête négative peut être parcourue dans les deux sens. Si les parcours peuvent répéter les liaisons, l'aller-retour crée immédiatement un coût négatif répétable. Les problèmes de chemins simples, qui interdisent les répétitions, ont une autre formulation. Bellman-Ford traite ici les parcours usuels où les répétitions sont possibles.
La distance initiale vaut zéro pour la source S et l'infini ailleurs. Un premier passage examine les trajets utilisant au plus un arc. Le suivant autorise un arc supplémentaire. À chaque étape, on conserve aussi les anciennes valeurs : « au plus » signifie qu'un chemin déjà trouvé peut rester le meilleur sans employer tout le nombre d'arcs autorisé.
Une implantation en place réutilise immédiatement les améliorations. Elle reste valable pour Bellman-Ford, mais ses tableaux intermédiaires dépendent de l'ordre des arcs et ne signifient plus exactement « au plus k arcs ». Pour expliquer les chiffres sans ambiguïté, notre trace utilise la version synchrone.
d[S] ← 0 ; toutes les autres distances ← infini
Répéter au plus n − 1 fois :
nouveau ← copie de d
Pour chaque arc (u, v, poids) :
Si d[u] est fini et d[u] + poids < nouveau[v] :
nouveau[v] ← d[u] + poids
mémoriser la provenance de cette amélioration
Si nouveau = d : arrêter les passages
d ← nouveau
Tester encore tous les arcs pour détecter une amélioration possibleNotre exemple orienté possède les sommets S, A, B, C et T. Les arcs sont SA de poids 4, SB de poids 5, AC de poids 3, BA de poids −4, BC de poids 6, CT de poids 2 et AT de poids 10. Le sens des arcs interdit de revenir de A vers B. La remise BA peut donc être utilisée sans créer une répétition avantageuse.
| Passage | S | A | B | C | T |
|---|---|---|---|---|---|
| 0 | 0 | ∞ | ∞ | ∞ | ∞ |
| 1 | 0 | 4 | 5 | ∞ | ∞ |
| 2 | 0 | 1 | 5 | 7 | 14 |
| 3 | 0 | 1 | 5 | 4 | 9 |
| 4 | 0 | 1 | 5 | 4 | 6 |
Au premier passage, seuls A et B deviennent accessibles avec les valeurs 4 et 5. Au deuxième, B améliore A à 1, mais C utilise encore l'ancienne valeur de A et reçoit 7. T reçoit 14 par A. Cette étape est souvent mal lue : la copie des distances empêche de traverser plusieurs nouveaux arcs dans un seul passage.
Au troisième passage, C atteint 4 grâce à A, et T atteint 9 grâce à l'ancienne valeur de C. Au quatrième, T atteint 6. Les distances finales sont S : 0, A : 1, B : 5, C : 4, T : 6. Le trajet S–B–A–C–T coûte bien 5 − 4 + 3 + 2 = 6.
Le lien avec les passages devient immédiat. La version synchrone connaît tous les meilleurs coûts utilisant au plus un arc supplémentaire à chaque passage. Après n − 1 passages, elle inclut donc au moins un chemin optimal vers chaque sommet dont la distance minimale est finie. Les sommets inaccessibles restent à l'infini.
Le raisonnement suppose qu'aucun cycle négatif accessible ne permet d'améliorer le trajet. Sans cette hypothèse, retirer un cycle pourrait au contraire augmenter le coût. C'est pour cela que Bellman-Ford effectue un test supplémentaire plutôt que d'annoncer toujours les valeurs obtenues comme des minima.
Un passage sans aucune amélioration permet un arrêt anticipé : appliquer encore les mêmes relaxations aux mêmes distances ne changera rien. Cette optimisation améliore beaucoup certains cas pratiques, mais ne réduit pas la borne du pire cas. Il faut aussi conserver le test de cycle lorsque les passages se poursuivent jusqu'à la limite prévue.
Considérons maintenant SA de poids 2, AB de poids 1, BA de poids −3 et BT de poids 2. Le circuit A–B–A coûte −2. Il est accessible depuis S et permet ensuite de rejoindre T. Les valeurs successives du calcul continuent donc à baisser ; une nouvelle amélioration reste possible après les passages normalement suffisants.
Ici, A, B et T ont des coûts non bornés inférieurement. On les note symboliquement −∞ : ce n'est pas un nombre à additionner dans un programme ordinaire, mais un statut. S garde la distance zéro, car aucun arc ne permet de revenir vers S. Un cycle négatif situé dans une zone inaccessible depuis S ne changerait aucune distance depuis cette source.
Pour déterminer tous les sommets affectés, on repère les destinations encore améliorables, puis on explore leurs descendants. Tout sommet atteignable après un cycle négatif peut profiter d'un nombre arbitraire de répétitions avant de poursuivre vers sa destination. Les valeurs finies observées dans les derniers tableaux sont seulement des états de calcul ; elles ne doivent pas être publiées comme des solutions optimales.
La version de base effectue jusqu'à n − 1 passages sur m arcs, puis un dernier test. Sa partie principale coûte O(nm), à laquelle s'ajoute l'initialisation O(n). Les deux tableaux de distances utilisent O(n) de mémoire auxiliaire. Garder tout l'historique pour l'enseignement ou la reconstruction par couches demande O(n²) de mémoire supplémentaire ; ce choix n'est pas nécessaire pour obtenir les seules distances.
Chaque relaxation vérifie d'abord que le départ est accessible. On n'additionne pas un poids à une valeur sentinelle représentant l'infini. Avec des nombres machine, il faut prévenir les débordements ; avec des décimaux approchés, la comparaison de petites améliorations demande une politique numérique cohérente. Modifier arbitrairement les comparaisons peut masquer un véritable cycle négatif.
Bellman-Ford est plus coûteux que Dijkstra sur beaucoup de réseaux positifs. Son intérêt est d'accepter les poids négatifs et de fournir un diagnostic lorsqu'un minimum fini n'existe pas. Le bon algorithme est donc celui dont les hypothèses correspondent aux données, pas celui dont le nom semble le plus général.
Pourquoi C reçoit-il 7 au deuxième passage alors que A y descend à 1 ?
La mise à jour de C lit la valeur précédente de A, qui vaut encore 4 dans le tableau de départ du passage. Le trajet SA puis AC coûte donc 7. La nouvelle valeur 1 de A sera exploitable au passage suivant.
Calculez le coût de S–B–A–C–T dans l'exemple sans cycle.
On additionne 5, −4, 3 et 2 : le total vaut 6. Le signe négatif diminue le coût sans créer de répétition, car aucun retour vers B n'est autorisé. Le résultat concorde avec le dernier tableau de Bellman-Ford.
Dans l'exemple du circuit A–B–A, pourquoi T est-il affecté mais pas S ?
On peut répéter le circuit avant de rejoindre T par BT, donc abaisser son coût sans limite. Aucun parcours ne revient vers S. Sa distance demeure zéro même si le cycle est accessible en partant de S.
Un réseau possède une liaison négative mais aucun cycle négatif. Peut-on choisir Dijkstra parce que le minimum existe ?
Non. L'existence d'un minimum ne suffit pas à justifier la finalisation de Dijkstra. Bellman-Ford accepte les poids négatifs et trouve les minima finis. Le contre-exemple du chapitre précédent est déjà sans cycle et fait pourtant échouer Dijkstra classique.
Questions / Réponses
Ajouter un commentaire