UNIVERSITE CHEIKH ANTA DIOP (UCAD)

ÉCOLE SUPÉRIEURE POLYTECHNIQUE (E.S.P)

DÉPARTEMENT DE GESTION

Recherche Opérationnelle

Chapitre: Théorie des Graphes

Algorithme de Bellman et Krushkal a

[Link]

17 juillet 2020
(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 1 / 16
Sommaire

1 Algorithme de Bellman

2 Algorithme de Djikstra

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 2 / 16

Algorithme de Bellman

Objectif
Trouver dans un graphe sans circuit, comportant des arcs valués
positivement ou négativement tous les chemins de longueurs extrémales
aboutissant à un sommet x0 du graphe.

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 3 / 16

Algorithme de Bellman

Objectif
Trouver dans un graphe sans circuit, comportant des arcs valués
positivement ou négativement tous les chemins de longueurs extrémales
aboutissant à un sommet x0 du graphe.

C’est en quelque sorte une recherche du plus court ou de plus long chemin
menant à ce sommet x0 partant de n’importe quelle autre sommet du
graphe.

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 3 / 16

Algorithme de Bellman

Recherche de plus court chemin (P.C.C)

Algorithme
1 Ordonnancer le graphe par niveaux ;
No = xo , affecter à x0 la quantité l0 = 0.
2 A chaque niveau, pour le sommet xj faire lj = min li + vij pour i tel
que xi est un précédent de xj et vij valuation de l’arc (xi , xj ).
3 Reconstruire le plus court chemin de x0 à un autre sommet en
”remontant”.
Recherche de plus long chemin (P.L.C)
Dans ce cas, il suffit,de remplacer dans l’étape 2 précédente l’expression
li = min {li + vij } par li = max {li + vij }
a

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 4 / 16

Algorithme de Bellman

Exemple
Chercher les plus courts chemins menant au sommet a du graphe suivant.
c

8 5
b 15 e
7 9

9 7 8 g
a
5 11
d 6 f
a

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 5 / 16

 Algorithme de Bellman

Solution de l’exercice
tape 1 Ordonnancement par niveau
g f d a
11 6 5

9 8 9
15
7

e 7 b
5
8

N N1 N2 N3 N4 N5
0

Initialisation
Partant du sommet a, notons P = {a}, T = {d, b}

tape 2 a

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 6 / 16

Algorithme de Bellman

Itération 1
On a lb = 7 et ld = 5 ; min{lb , ld } = 5 = ld ce qui correspond au sommet
d, donc on met à jour P : P = {a, d}.
L’ensemble des précédents des sommets de P est T = {b, e, f }

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 7 / 16

Algorithme de Bellman

Itération 1
On a lb = 7 et ld = 5 ; min{lb , ld } = 5 = ld ce qui correspond au sommet
d, donc on met à jour P : P = {a, d}.
L’ensemble des précédents des sommets de P est T = {b, e, f }

Itération 2
On a lb = 7, le = ld + ved = 5 + 15 = 20, lf = ld + vfd = 5 + 6 = 11.
min{lb , le , lf } = 7 = lb . Il s’en suit les mises à jour P = {a, d, b} et
T = {c, e, f }.

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 7 / 16

Algorithme de Bellman

Itération 1
On a lb = 7 et ld = 5 ; min{lb , ld } = 5 = ld ce qui correspond au sommet
d, donc on met à jour P : P = {a, d}.
L’ensemble des précédents des sommets de P est T = {b, e, f }

Itération 2
On a lb = 7, le = ld + ved = 5 + 15 = 20, lf = ld + vfd = 5 + 6 = 11.
min{lb , le , lf } = 7 = lb . Il s’en suit les mises à jour P = {a, d, b} et
T = {c, e, f }.

Itération 3
lc = lb + vcb = 15, le = min{lb + veb , ld + ved } = min{14, 20} = 14 et
lf = ld + vfd = 11.
On a min{lc , le , lf } = lf = 11. a
Mises à jour : P = {a, d, b, f } et T = {c, e, g } [Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 7 / 16

Algorithme de Bellman

Itération 4
lc = 15, le = 14 et lg = lf + vgf = 11 + 11 = 22.
On a min{lc , le , lg } = le = 14.
Mises à jour : P = {a, d, b, f , e} et T = {c, g }

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 8 / 16

Algorithme de Bellman

Itération 4
lc = 15, le = 14 et lg = lf + vgf = 11 + 11 = 22.
On a min{lc , le , lg } = le = 14.
Mises à jour : P = {a, d, b, f , e} et T = {c, g }

Itération 5
lc = 15 et lg = min{lf + vgf , le + vge } = min{22, 23} = 22.
On a min{lc , lg } = lc = 15.
Mises à jour : P = {a, d, b, f , e, c} et T = {g }

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 8 / 16

Algorithme de Bellman

Itération 4
lc = 15, le = 14 et lg = lf + vgf = 11 + 11 = 22.
On a min{lc , le , lg } = le = 14.
Mises à jour : P = {a, d, b, f , e} et T = {c, g }

Itération 5
lc = 15 et lg = min{lf + vgf , le + vge } = min{22, 23} = 22.
On a min{lc , lg } = lc = 15.
Mises à jour : P = {a, d, b, f , e, c} et T = {g }

Itération 6
Il ne reste que le sommet g de T. Avec lg = 22, on intègre g dans
l’ensemble P. D’où P = {a, d, b, f , e, c, g }.
Les plus courts chemins menant au sommet a sont donnés dans le graphea
suivant [Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 8 / 16

Algorithme de Bellman

g f d a
11 6 5

e b 7
7

8
c

Figure : Graphe des plus courts chemins de l’exercice

a

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 9 / 16

Algorithme de Djikstra

Objectif :
Trouver dans un graphe orienté G = (S, A) valué positivement, pouvant
comporter un circuit, tous les chemins de longueurs extrémales quittant un
sommet x0 vers tout autre sommet du graphe.

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 10 / 16

Algorithme de Djikstra

Recherche de plus courts chemins (P.C.C) :

Méthode
On définit la valeur l : A → R+ , et pour tout x ∈ A, on cherche le
minimum sur tous les chemins de x0 à x de la somme des valuations des
arcs du chemin. On construit un ensemble P ⊂ S tel que le P.C.C de x0 à
tout autre sommet de P soit constitué de sommets de P. Algorithme
Soit x0 le sommet par rapport auquel le P.C.C est calculé. Pour tous les
sommets xi et xj on pose :

 l(xi , xj ) ≥ 0 si (xi , xj ) ∈ A
l(xi , xi ) = 0
l(xi , xj ) = +∞ si (xi , xj ) ∈
/A


[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 11 / 16

 Algorithme de Djikstra

Recherche de plus courts chemins (P.C.C) :

tape 0 : Initialisation
Poser P = {x0 }, D[x0 ] = 0 ;
Pour xi 6= x0 , faire D[xi ] = l(x0 , xi ).
tape 1 Si P = S, alors fin,
sinon : soit xj tel que xj ∈ S \ P et D[xj ] soit le minimum des D[xi ]
(c-à-d D[xj ] = min D[xi ]),
alors P = P ∪ {xj }
tape 2 Pour tout xi ∈ S\P, faire
D[xi ] = min{D[xi ], D[xj ] + l(xj , xi )}
Retourner à l’étape 1.

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 12 / 16

Algorithme de Djikstra

Exemple
Appliquer l’algorithme de Dijkstra pour chercher le P.C.C du sommet g à
tout autre sommet du graphe ci-après :
f d

g
a

b
e

Figure : Graphe G(S,A)

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 13 / 16

Algorithme de Djikstra

Solution
La résolution peut être faite sous forme tabulaire : on construit un tableau
dont la première ligne comporte les sommets du graphe. Le tableau est
rempli ligne après ligne. A partir de la deuxième ligne, le premier élément
de chaque ligne comporte le sommet xi donnant le PCC à l’étape
considérée. Les valuations l(xi , xj ) des arcs (s’il en existe) liant le sommet
xi à tout autre sommet xj remplissent les autres cellules de la ligne (sauf
les deux dernières). L’avant dernière colonne donne la valeur du PCC
tandis que dans la dernière colonne sont stockés l’ensemble des précédents
du sommet auquel abouti le PCC. Cette dernière colonne permet de
retrouver les PCC.

[Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 14 / 16

Algorithme de Djikstra
S-G
a b c d e f g PCC Précédent(s
S-PCC
g - - - - 9 11 0 Dg = 0 néant
De = lge
e - 7 5 15 0 - - g
=9
Df = lgf
f - 5 - 6 - 0 - g
= 11
De = De +
c - 8 0 - - - - e
lec = 11
Db = De +
d 7 0 - - - - - leb = Df e,f
+lfb = 16
Dd = Df +
d 5 9 - 0 - - - f
lfd = 17
Da = Dd +
a 0 - - - - - - da
lda = 22 [Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 15 / 16

Algorithme de Djikstra
Résultat graphique
f d

g
a

b
e

Figure : Résultat graphique de l’algorithme

Remarque 1.9 Une fois un sommet sélectionné, dans le PCC (i.e. la

première colonne), on peut alors rayer le restant des cellules se trouvant
dans la colonne réservée au sommet qui vient d’être sélectionné. zéro. Les
plus courts chemins ayant pour origine le sommet g sont donnés dans le a
graphe suivant. [Link]

(ESP/UCAD Mail : esp@[Link]) 17 juillet 2020 16 / 16