Scribd
Importer
74 vues5 pages

Algorithme de Bellman et applications

Transféré par

Younesse El
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
74 vues5 pages

Algorithme de Bellman et applications

Transféré par

Younesse El
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Algorithme

de Bellman
C’est une généralisation de l’algorithme de Dijkstra
(Ici le poid de l’arc (i,j) est de signe quelconque)
CNS

La CNS d’existence de plus court chemin est qu’il n’existe pas de


circuit absorbant dans le graphe G
( une boucle de longueur <= 0)
Etapes de l’algorithme de BELLMAN

(G,C,s): ( Graphe,arc,point initial)


Initialisation
d(s) 0
Pour chaque arc v de C sauf (s) faire d(v) ∞

Itérations
Pour i de 1 à n-1 faire ( n le nombre de sommet de G)
Pour chaque arc (u,v) de G faire
Si d(v) > d(u)+C(u,v) alors d(v) d(u)+C(u,v)
Fin
Fin
Contrôle de la présence d’une boucle négative
Pour chaque arc (u,v) de G si d(v) > d(u)+C(u,v) alors existence d’une boucle négative
Sinon retour à d(v)
Application 1

Utiliser l’algorithme de Bellman pour trouver le plus court chemin entre A et F du graphe suivant:
Application 2

Vous aimerez peut-être aussi