Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
112
tandis que le som    met en cours de trai    te    ment est cer    clé d’un filet épais. Les arcs modi  ­
fiant les valeurs l i sont repré sen tés en gras les sommets situés à gauche des traitillés
sont ceux dont le l est définitif. Sur la der    nière figure (en bas) les arcs en gras sont 
ceux uti    li    sés lors de la der    nière modi    fi    ca    tion des valeurs l i . En remon tant ces arcs
nous obte nons l’arbo res cence des plus courts che mins issus du som met A.
Figure 4.11 Exemple d’exé cu tion de l’algo rithme de Dijkstra
Arborescence des
plus courts chemins
(réduite ici à un chemin hamiltonien)
Le chemin de valeur minimale de A à C est :
(A, E, D, B, C) qui “coûte” λ c = 6.