Discussion :

[jcaspar]

Bonjour à tous !

Je souhaiterais convertir l'algorithme de ford (theorie des graphes )
en programme informatique

voici le pseudo code

;~ booléen Bellman_Ford(G, s)
;~
;~ initialisation (G, s) // les poids de tous les sommets sont mis à +infini
;~ // le poids du sommet initial à 0
;~ pour i=1 jusqu'à Nombre de sommets -1 faire
;~ | pour chaque arc (u, v) du graphe faire
;~ | | paux := poids(u) + poids(arc(u, v));
;~ | | si paux < poids(v) alors
;~ | | | pred(v) := u;
;~ | | | poids(v) := paux;
;~ pour chaque arc (u, v) du graphe faire
;~ | si poids(u) + poids(arc(u, v)) < poids(v) alors
;~ | retourner faux
;~ retourner vrai


malheureusement je ne comprends pas très bien ce pseudo code ...
pourriez vous svp m'expliquer le deroulement et les différentes étapes de l'algorithme ?


Je vous remercie d'avance pour votre aide et vos conseils

[Aldiemus]

Bonjour,

Si mes souvenirs sont bons, ce genre d'algorithme sert à récupérer le plus cours chemin dans un graphe.

Tu commences par initialiser tous les points avec un poids infini, pour être sûr que si tu as une possibilité d'aller vers ce point, elle est forcément mieux que l'infini. En terme d'implémentation, il s'agit de mettre en place une valeur qui te permet de savoir qu'un sommet n'a pas encore été atteint. Si les valeurs de tes arcs sont toutes positives, tu peux utiliser -1 par exemple.

Par exemple, tu vas avoir l'arc entre P4 et P5 a un poids de 4. Il faut donc ajouter 4 au poids de P4 pour arriver à P5 par cet arc. Or, si le poids de P4 + 4 est supérieur au poids de P5 que l'on a déjà trouvé par un autre chemin, on le laisse tomber, il y a déjà un meilleur chemin. Et tu continues comme ça.

Si par contre, tu a trouvé un meilleur chemin, tu sauvegardes le poids (pour pouvoir le recomparer à un autre chemin que tu vas calculer par la suite) ainsi que le point précedent, ce qui va te permettre de recomposer ton chemin. C'est ce que tu fais là :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
;~ | | si paux < poids(v) alors
;~ | | | pred(v) := u;
;~ | | | poids(v) := paux;

Pour l'implémentation, tu as plusieurs choix. Soit tu te fixes un point de départ qui vaut un poids 0 et tu cherches les points à atteindre à partir de ce point. Soit tu peux procéder par récurcivité. Par exemple le poids de P5 c'est le poids de P4 + 4, oui mais le poids de P4 c'est le poids de P2 +5, etc....

J'espère que j'ai pû t'aider.

Bonne journée,

Aldiemus