Scribd
Importer
426 vues9 pages

Algorithme de Bellman-Ford et applications

L'algorithme de Bellman-Ford permet de trouver le plus court chemin dans un graphe où les arcs peuvent avoir un poids négatif. Il consiste à mettre à jour les estimations des distances à chaque itération jusqu'à ce qu'il n'y ait plus de mise à jour possible ou qu'un circuit absorbant soit détecté.

Transféré par

Imane el omari
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
426 vues9 pages

Algorithme de Bellman-Ford et applications

L'algorithme de Bellman-Ford permet de trouver le plus court chemin dans un graphe où les arcs peuvent avoir un poids négatif. Il consiste à mettre à jour les estimations des distances à chaque itération jusqu'à ce qu'il n'y ait plus de mise à jour possible ou qu'un circuit absorbant soit détecté.

Transféré par

Imane el omari
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-Ford
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 d’un chemin optimal:

PCC:
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
PCC

(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:

Peut-on calculer le plus long chemin entre A et F ? Ecrire toutes les itérations et conclure.
Correction de l’application 1

Itération A B C D E F Plus
court
chemin
de A
vers F
Initialisatio 0 ∞ ∞ ∞ ∞ ∞
n d(v)
1 0 (3 ;A) (4 ;A) ∞ ∞ ∞ A

2 0 (3 ;A) (4 ;A) (-1,C) (5 ;B) ∞ C

3 0 (-3 ;D) (4 ;A) (-1,C) (5 ;B) (2 ;D) D

4 0 (-3 ;D) (4 ;A) (-1,C) (-1 ;B) (2 ;D) B

0 (-3 ;D) (4 ;A) (-1,C) (-1 ;B) (0 ;E) E


5

Contrôle de 0 -3 4 -1 -1 0
Non
existence
d’une
boucle
négative
Ligne 5 ∩ {F}=E
Ligne 4 ∩ {E}=B
Ligne 3 ∩ {B}=D
Ligne 2 ∩ {D}=C
ligne 1 ∩ {C}=A

Donc le plus court chemin entre A et F est :


A→C→ 𝐷 → B → E →F

On fait le même raisonnement avec A et n’importe quel autre sommet du


graphe.
Application 2 : Fiabilité d’un circuit

Dans un graphe G = (X, A), on associe à tout arc (i, j ) de A une "fiabilité" rij c'est à dire
une valeur comprise entre 0 et 1 : 0 < rij ≤ 1.

La fiabilité mesure la probabilité que l'arc soit opérationnel (c'est-à-dire non


défaillant).

On définit la fiabilité d'un chemin P du graphe G, comme le produit des fiabilités des
arcs qui forment ce chemin :

Le problème est de déterminer le (ou les) chemin(s) de fiabilité maximale issus d'un
sommet source s vers tout autre sommet du graphe.
Chercher la fiabilité maximale entre A et F du graphe suivant:
(Utiliser la fonction log pour se ramener à un PCC. On rappelle que pour 0<rij<=1, log
(rij)<=0)

0,8
B E
0,4 0,3
0,5 0,1
A 0,2
F

0,7
0,6
C D
0,2 C
Application 5

Déterminer le PCC entre S1 et S4 du graphe suivant

Vous aimerez peut-être aussi