cours 4

CHAPITRE II Problème du plus court chemin

Cours 4

2. Algorithme de Bellman-Ford :

L'algorithme de Bellman-Ford est un algorithme de programmation dynamique qui permet de trouver les plus courts chemins, depuis un sommet source donné, dans un graphe orienté pondéré. Contrairement à l'algorithme de Dijkstra, qui ne peut être utilisé que lorsque tous les arcs ont des poids positifs ou nuls, l'algorithme de Bellman-Ford autorise la présence de certains arcs de poids négatif et permet de détecter l'existence d'un circuit absorbant, c'est-à-dire de poids total négatif, accessible depuis le sommet source.

< Richard Ernest Bellman, né le 29 août 1920 à Brooklyn et mort le 19 mars 1984 à Los Angeles, est un mathématicien américain. Célèbre pour diverses contributions dans plusieurs domaines des mathématiques, il est surtout l'inventeur de la programmation dynamique. Lester Randolph Ford junior >, né le 23 septembre 1927 à Houston est un mathématicien americain spécialiste des problèmes des réseaux de transport.2.1 Objectif de l'algorithme de Bellman-Ford :Chercher dans un réseau (graphe) les plus courts chemins qui relient un sommet de départ s_deb à tous les autres sommets du graphe. 2.2 Description de l'algorithme de Bellman-Ford :

pour tout sommet s ∈ S faire // Initialisation

d[sdeb] ← 0

d[s] ← ∞ ∀ s ≠ sdeb

Γ ^-1[s] ← NIL

Fin pour

pour i de 1 à |S| − 1 faire // Itérations

pour tout arc (u, v) ∈ A faire

si d[v] > d[u] + w(u, v) alors

d[v] ← d[u] + w(u, v)

Γ ^-1[v] ← u

Fin si

Fin pour

Fin pour

pour tout arc (u, v) ∈ A faire // détection des circuits négatifs

si d[v] > d[u] + w(u, v) alors

écrire ("circuit négatif détecté")

sinon d[v] ; Γ ^-1[v]

Fin si

Fin pour

2.3 Principe de l'algorithme de Bellman-Ford :

A partir de d(s_deb) = 0 et d(s) = ∞ ∀ s ≠ s_deb, on parcourt séquentiellement tous les arcs du graphe : pour chaque arc uv on teste si d(v) ≤ d(u) + w(u, v) si ce n’est pas le cas d(v) prend la valeur d(u) + w(u, v), puis on teste l’arc suivant. Si, à l’issue d’un deuxième parcours, d n’est pas modifié, il représente les distances cherchées sinon un parcours supplémentaire est nécessaire et cela jusqu’à stabilisation de d

2.4 Exemple d'application

Solution :

Le sommet de début est A :

Etape 1 Initialisation :

Sdeb= {A}, donc la distance de A vers A est nulle => d[A]=0.

Mais pour les autres sommets la valeur par défaut est ∞ :

d[B]= ∞ | Γ ^-1[B]=NIL

d[C]= ∞ | Γ ^-1[C]=NIL

d[D]= ∞ | Γ ^-1[D]=NIL

Etape 2 itérations :

I=1 :

AC= [∞,0+4] => d[C]=4 (on a pris le minimum entre l’ancienne d[C] et la somme de d[A] avec le poids entre A et C ) Γ ^-1[C]=A

CA= [0,4+2] => d [A]= 0

CD= [∞,4+5] => d [D]= 9 et Γ ^-1[D]=C

DC= [4,9+3] => d [C]= 4

BC= [4, ∞+3] => d [C]= 4

CB= [∞,4+2] => d [B]= 6 et Γ ^-1[B]=C

AB= [6, 0+7] => d [B]= 6

DB= [6, 9+3] => d [B]= 6

I=2 :

AC= [4,0+4] => d[C]= 4

CA= [0,4+2] => d [A] = 0

CD= [∞,4+5] => d [D]= 9

DC= [4,9+3] => d [C]= 4

BC= [4, 6+3] => d [C]= 4

CB= [6,4+2] => d [B]= 6

AB= [6, 0+7] => d [B]= 6

DB= [6, 9+3] => d [B]= 6

Conclusion :

On a trouvé le plus court chemin entre le sommet de début A et tous les autres sommets tq :

de A à B : d[B]= 6 donc : A---->C---->B

de A à C : d[C]= 4 donc : A---->C

de A à D : d[D]= 9 donc : A---->C---->D

Merci à K.K.S