EPFL RECHERCHE OPÉRATIONNELLE
Institut de Mathématiques GC
Prof. M. Bierlaire ÉTÉ 2006
CORRIGÉ DE LA SÉRIE D’EXERCICES 9
Problème 1
a) Le déroulement de l’algorithme est résumé dans le tableau suivant :
Itération V d1 d2 d3 d4 d5 d6 Traiter
1 {1} 0 ∞ ∞ ∞ ∞ ∞ 1
2 {2,3,4} 0 3 5 6 ∞ ∞ 2
3 {3,4,5} 0 3 5 6 4 ∞ 5
4 {3,4} 0 3 5 6 4 ∞ 3
5 {4,5} 0 3 5 6 3 ∞ 5
6 {4} 0 3 5 6 3 ∞ 4
7 {6} 0 3 5 6 3 8 6
8 ∅ 0 3 5 6 3 8
b) En effet, le sommet 5 est traité deux fois. Ceci provient du fait qu’une hypothèse sur le
réseau n’est pas vérifiée : le poids de l’arc (3,5) est négatif. On remarque néanmoins que
l’algorithme fonctionne correctement et fournit les plus courts chemins depuis 1.
Problème 2
La pondération étant non négative, l’algorithme de Dijkstra peut être utilisé pour déterminer un
plus court chemin du sommet 1 à tous les autres. Les étapes de l’application de cet algorithme
sont résumées dans le tableau suivant (les couples en dessous des sommets correspondent aux
marques λi et pi ) :
Itér. imin 1 2 3 4 5 6 7 8
0 0 - ∞ - ∞ - ∞ - ∞ - ∞ - ∞ - ∞ -
1 1 0 - 4 1 ∞ - ∞ - ∞ - ∞ - 3 1 ∞ -
2 7 4 1 ∞ - ∞ - ∞ - ∞ - 3 1 9 7
3 2 4 1 ∞ - 7 2 6 2 ∞ - 9 7
4 5 ∞ - 7 2 6 2 ∞ - 9 7
5 4 ∞ - 7 2 ∞ - 9 7
6 8 ∞ - ∞ - 9 7
Les plus courts chemins sont :
– de 1 à 2, de longueur 4 : 1 −→ 2 ;
– de 1 à 3 : il n’en existe pas ;
– de 1 à 4, de longueur 7 : 1 −→ 2 −→ 4 ;
– de 1 à 5, de longueur 6 : 1 −→ 2 −→ 5 ;
– de 1 à 6 : il n’en existe pas ;
– de 1 à 7, de longueur 3 : 1 −→ 7 ;
– de 1 à 8, de longueur 9 : 1 −→ 7 −→ 8.
1
Problème 3
Il faut résoudre le problème des plus courts chemins du sommet v 1 aux autres sommets du
réseau. L’algorithme générique vu au cours fournit le tableau suivant :
Itération Candidats L Étiquettes λ Sommet retiré de L
0 {v1 } (0,∞,∞,∞,∞)
1 {v2 ,v4 } (0,2,∞,1,∞) v1
2 {v3 ,v4 } (0,2,6,1,∞) v2
3 {v2 ,v3 ,v5 } (0,0,6,1,5) v4
4 {v2 ,v5 } (0,0,6,1,5) v3
5 {v3 ,v5 } (0,0,4,1,5) v2
6 {v5 } (0,0,4,1,3) v3
7 ∅ (0,0,4,1,3) v5
Les plus courts chemins et leurs longueurs sont, respectivement
λ∗ (v1 ) = 0 1
∗
λ (v2 ) = 0 1→4→2
∗
λ (v3 ) = 4 1→4→2→3
∗
λ (v4 ) = 1 1→4
λ (v5 ) = 3
∗
1→4→2→3→5
15 juin 2006 – mbi/mt/mts
