L_GLSI_2
L_BD_2
Université Centrale
L_IMM_2 Corrigé TD3 2022/2023
Exercice 1.
Le graphe ci-dessous correspond à des parcours possibles pour aller d'un point s à un point p.
1. Quel est le plus court chemin de s à p ?
Il n’existe pas de circuits on applique l’algorithme de BELLMAN
Initialisation : π(S)=0 ; Z={S}; A=
It1 : π(A)=1 ; Z={S,A}; A={(SA)}
It2 : π(D)=Min( π(S)+d(SD); π(A)+d(AD))=2 ; Z={S,A,D}; A={(SA),(SD)}
It3 : π(B)=Min( π(D)+d(DB); π(A)+d(AB))=4 ; Z={S,A,D,B}; A={(SA),(SD),(AB)}
π(G)=Min( π(S)+d(SG); π(D)+d(DG))=4 ; Z={S,A,D,B,G};
A={(SA),(SD),(AB),(SG)}
It4 : π(E)=Min( π(D)+d(DE); π(B)+d(BE), π(G)+d(GE))=6; Z={S,A,D,B,G,E};
A={(SA),(SD),(AB),(SG),(DE)}
It5 : π(H)=Min( π(E)+d(EH); π(G)+d(GH))=6; Z={S,A,D,B,G,E,H};
A={(SA),(SD),(AB),(SG),(DE),(GH)}
It6 : π(P)=Min( π(E)+d(EP); π(H)+d(HP); π(B)+d(BP))=7; Z=X;
A={(SA),(SD),(AB),(SG),(DE),(GH),(HP)}
2. Quel est le plus long chemin de s à p ?
On applique la fonction de maximisation au lieu de la fonction de minimisation en suivant le même
principe de la question 1
Tarek El Falah Page 1 sur 4
L_GLSI_2
L_BD_2
Université Centrale
L_IMM_2 Corrigé TD3 2022/2023
Exercice 2.
Soit le graphe suivant :
1. En utilisant l’algorithme de Bellman-Ford (algorithme général), trouver le chemin de valeur
maximale allant du sommet A vers tout autre sommet.
Trouver le chemin de valeur maximale allant du sommet A vers tout autre sommet. Justifier
le choix de l’algorithme utilisé.
Il existe un circuit : ((CB),(BC)) on ne peut pas appliquer l’algorithme de Bellman
Il existe un arc ayant une longueur strictement négative (l(CB)=-6) On ne peut pas
appliquer l(algorithme de Dijkstra
On applique alors l’algorithme de Bellman-Ford
Itération π(A) π(B) π(C) π(D) π(E)
It1 0 4/A 8/A -∞ -∞
It2 0 4/A 8/A,B 7/B 9/C,D
It3 0 4/A 9/D 7/B 10/C
It4 0 4/A 9/D 7/B 10/C
It4 = It3 convergence de l’algorithme de Bellman-Ford
Le chemin le plus long est le chemin hachuré sur le réseau
(AB),(BD), (DC), (CE))
Tarek El Falah Page 2 sur 4
L_GLSI_2
L_BD_2
Université Centrale
L_IMM_2 Corrigé TD3 2022/2023
Peut-on déterminer un chemin de valeur minimale de A vers E ? Si oui, lequel ? Sinon,
pourquoi ?
Non, on ne peut pas déterminer un chemin de valeur minimale de A vers E car il existe un
circuit absorbant ((CB),(BC)) ayant une longueur -2<0
Exercice 3.
Une région est munie d'un réseau de trains, représenté par le graphe G ci-dessous.
Les stations sont symbolisées par les sommets A, B, C, D, E, F et G. Chaque arête représente une
ligne reliant deux gares. Chaque ligne reliant deux stations comporte deux voies : une voie pour
l’aller et une autre pour le retour. Les temps de parcours (correspondance comprise) en minutes
entre chaque sommet ont été rajoutés sur le graphe.
1. Déterminer le plus court chemin en minutes, reliant la gare B à la gare G. Justifier la réponse
grâce à l’algorithme de Dijkstra.
Itération π(b) π(a) π(c) π(d) π(e) π(f) π(g) xp A(xp) Z
init 0 +∞ +∞ +∞ +∞ +∞ +∞ b - {b}
It1 0 4 7 +∞ 21 +∞ +∞ a (ba) {b,a}
It2 0 4 7 +∞ 21 +∞ +∞ c (bc) {b,a,c}
It3 0 4 7 +∞ 21 32 +∞ e (be) {b,a,c,e}
It4 0 4 7 36 21 31 38 f (ef) {b,a,c,e,f}
It5 0 4 7 36 21 31 38 d (ed) {b,a,c,e,f,d}
It6 0 4 7 36 21 31 38 g (eg) X
((ba), (bc), (be),(ef), (ed),(eg)) est une arborescence de plus courts chemin issue de B.
Tarek El Falah Page 3 sur 4
L_GLSI_2
L_BD_2
Université Centrale
L_IMM_2 Corrigé TD3 2022/2023
2. Quelle est la longueur en minutes de ce chemin ?
Le chemin dure 38 minutes.
Tarek El Falah Page 4 sur 4
