Algorithme de Bellman

[sylost]

Bonjour,

Je n'arrive pas à bien cerner ce que fait Bellman pour trouver le chemin le plus court, et je dois faire un programme qui puisse appliquer cet algorithme sur un graphe =/

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

Si quelqu'un pouvait m'expliquer en gros ce que ça fait =)

Ce que j'ai compris c'est que ça initialise les poids de tous les sommets à + l'infini, sauf pour le sommet initial qui se retrouve à 0, et qu'ensuite ça parcourt tous les arcs, mais après je pige plus :hein:

[Clembou]

Bonjour,

Je n'arrive pas à bien cerner ce que fait Bellman pour trouver le chemin le plus court, et je dois faire un programme qui puisse appliquer cet algorithme sur un graphe =/


Si quelqu'un pouvait m'expliquer en gros ce que ça fait =)

Ce que j'ai compris c'est que ça initialise les poids de tous les sommets à + l'infini, sauf pour le sommet initial qui se retrouve à 0, et qu'ensuite ça parcourt tous les arcs, mais après je pige plus :hein:

Bonjour,

Ca pourrait t'aider : http://www.fil.univ-lille1.fr/%7Eboulier/ALGO/support.pdf