Consigne
- Le graphe est orienté et certains poids sont négatifs : l'algorithme de Dijkstra ne marcherait pas, on utilise Bellman-Ford.
- À 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.
- 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.
- 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. - 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.