L3 Informatique/MIAGE 2021–2022
TD7 : Recherche du plus court chemin dans un graphe orienté
— Rappel : cas des valeurs positives sur les arcs —
Algorithm 1 Dijkstra (G, l, s)
Require: Graph G = (V, E) with positive edge weights {le > 0 : e ∈ E} and s ∈ V .
Ensure: ∀u ∈ V, dist(u) is set to the shortest distance from s to u; prev(u) points to the previous
of u on this shortest path.
1: for u ∈ V do
2: dist(u) ← ∞
3: prev(u) ← nil
4: end for
5: dist(s) ← 0
6: P ← ∅ . P contains the vertices v, such that dist(v) is definitively computed.
7: T ← V . T contains the vertices v, such that dist(v) is only an upper bound.
8: while T 6= ∅ do
9: u ← argmin dist(v)
Sv∈T
10: P ← P {u}
11: T ← T \ {u}
12: for (u, v) ∈ E do
13: if dist(v) > dist(u) + l(u, v) then
14: dist(v) = dist(u) + l(u, v)
15: prev(v) ← u
16: end if
17: end for
18: end while
19: return (dist, prev)
Exercice 1 (Algorithme de Dijkstra).
1. Appliquer l’algorithme de Dijkstra (Algorithme 1) au graphe de la figure 1 afin de
calculer les chemins de poids minimal entre A et les autres sommets du graphe.
À la fin du calcul :
— chaque sommet i sera associé à un couple (dist(i), prev(i)) ;
— l’arborescence des chemins les plus courts de A sera mise en évidence sur le
graphe (exemple : mise en gras des arcs concernés).
2. Quelle est la relation entre dist(x), dist(y) et l(x, y) pour tout arc (x, y) de l’arbo-
rescence fabriquée par l’algorithme de Dijkstra ? Notons cette relation R.
3. Montrer à l’aide d’un exemple que lorsque les poids peuvent être négatifs, l’algorithme
de Dijkstra ne donne pas nécessairement les plus courts chemins. Est-ce que la relation
R est vraie dans ce cas aussi ?
1
1000 20
A C E
700 327
250 334
B D F
150 1001
Figure 1 – Graphe pour l’exercice 1 Figure 2 – Graphe avec des arcs pon-
. dérés dans Z
Exercice 2 (Chemin de valeur optimale dans un graphe avec des arcs de longueur/poids
quelconque). On considère le graphe de la figure 2
1. On cherche à obtenir les chemins les plus courts permettant de rejoindre tous les
sommets du graphe à partir de a. Quels sont les algorithmes vus en cours pour
résoudre ce problème ? Connaissez-vous plusieurs variantes de ces algorithmes ? Si
oui, appliquer la variante dont les conditions d’application sont vérifiées.
2. Comment modifier cet algorithme de façon à résoudre le problème de recherche des
chemins les plus longs ? À quelle condition cet algorithme est-il applicable ?
Appliquer l’algorithme modifié sur le graphe ci-dessus.
3. En ajoutant une constante suffisamment grande au poids de chaque arc, on peut
rendre ce poids positif. On décide alors d’appliquer l’algorithme de Dijkstra au nou-
veau graphe pondéré pour trouver les plus courts chemins de a à tout sommet. Cette
idée est-elle bonne ? Justifiez.
4. On considère maintenant un graphe pondéré où tous les poids ont une valeur négative.
En considérant l’opposé des poids, peut-on résoudre le problème du plus court chemin
à l’aide de l’algorithme de Dijkstra ?
5. Pour un graphe quelconque, comment modifier l’algorithme de Dijkstra de façon à
ce qu’il trouve le chemin le plus court du sommet initial a à un sommet t supposé
donné ?
6. Pour un graphe quelconque, comment modifier l’algorithme considéré dans la pre-
mière question pour faire la même chose ?
2
Exercice 3. On considère le graphe défini par la matrice d’adjacence suivante :
a b c d e f g h
a 1 1 1 1
b 1 1 1
c 1 1
d 1
e 1 1 1
f 1 1
g 1
h
Ce graphe est pondéré, mais un accident a fait disparaître presque toutes les informations
sur la valeur des arcs. Cependant, on sait que :
1. Toutes les valeurs sont entières, non négatives ;
2. La valeur de l’arc (e, d) est égale à 5 ;
3. Les valeurs minimales disti des chemins de a à i (calculées en additionnant les valeurs
des arcs) sont égales à :
Sommet a b c d e f g h
dist 0 8 7 15 10 3 13 20
4. Dans l’arborescence des chemins de valeur minimale issus de a, on a prevh = g,
prevg = b. Cette arborescence est unique.
Déterminer l’arborescence des chemins de valeur minimale issus de a (en particulier la
valeur des arcs qui la composent), ainsi qu’un minorant de la valeur des arcs qui n’appar-
tiennent pas à cette arborescence.
3
— Rappel : présence de valeurs négatives sur les arcs —
Algorithm 2 Bellman-Ford(G, l, s)
Require: Graph G = (V, E) with edge weights {le : e ∈ E} with no negative cycles and s ∈ V .
Ensure: ∀u ∈ V reachable from s, dist(u) is set to the shortest distance from s to u.
1: for u ∈ V do
2: dist(u) ← ∞
3: end for
4: dist(s) ← 0
5: k ← 1
6: while k ≤ |V | − 1 do
7: for (u, v) ∈ E do
8: dist(v) ← min {dist(v), dist(u) + l(u, v)}
9: end for
10: k ←k+1
11: end while
12: return dist
Algorithm 3 Bellman-Ford_bis(G, l, s)
Require: Graph G = (V, E) with edge weights {le : e ∈ E} and s ∈ V .
Ensure: ∀u ∈ V reachable from s, distk (u) is set to the shortest distance from s to u over all
paths with at most k arcs. It also detects the presence of negative cycle.
1: for u ∈ V do
2: dist0 (u) ← ∞
3: end for
4: dist0 (s) ← 0
5: stable ← f alse
6: k ← 1
7: while k ≤ |V | and ¬stable do
8: distk (s) ← 0
9: for v ∈ V \ {s} do
10: distk (v) = min {distk−1 (v), min distk−1 (u) + l(u, v)}
u∈Γ−1 (V )
11: end for ^
12: stable ← distk (v) = distk−1 (v)
v∈V
13: k ←k+1
14: end while
15: if k = |V | + 1 then
16: return there is at least one negative cycle
17: end if
18: return dist
