Algorithme de Bellman-Ford (graphe orienté,poids positif ou négatif): Plus long chemin
1. Marquer le sommet-initial = 0 et les autres = -∞
2. Pour chaqu' arête (X,Y), on maximise Y c'est-à-dire
si X+(X,Y) > Y alors on prend Y=X+(X,Y)
3. Tant qu'on peut maximiser, on le fait
4. On s'arrête quand on ne peut rien changer.
Cliquer à l'intérieur du graphe pour trouver le plus long chemin entre A et F
Résultat ?
Accueil