Algorithme de Bellman-Ford

SNT – Plus courts chemins depuis le sommet A (graphe orienté, poids négatifs possibles)

🏠 Accueil
Consigne
  1. Le graphe est orienté et certains poids sont négatifs : l'algorithme de Dijkstra ne marcherait pas, on utilise Bellman-Ford.
  2. À chaque itération, on passe en revue tous les arcs du graphe. Concrètement, regarde pour chaque sommet les arcs qui arrivent sur lui : si l'un d'eux donne un chemin plus court, la valeur du sommet change. Utilise les valeurs de l'itération précédente.
  3. Il y a au maximum n−1 itérations (n = nombre de sommets) : ici n−1 = . On s'arrête plus tôt si une itération ne change plus aucune valeur.
  4. Pour chaque sommet dont la valeur change, écris dans sa case la nouvelle valeur distance(sommet précédent), par exemple 5(B), -2(C), -2C. Laisse la case vide si la valeur ne change pas.
  5. Clique sur « Valider cette itération » (ou appuie sur Entrée). Les anciennes valeurs restent visibles, barrées ; les nouvelles ont la couleur de l'itération.
Les nombres sur les arcs sont les poids (négatifs en rouge). Chaque itération a sa couleur : les valeurs remplacées sont barrées.