Retour à la table des matières

Département de mathématiques de l'Université de La Rochelle

 

Activités sur le chapitre 1
Graphes eulériens

 

Activité 2 - Un algorithme de plus court chemin

Dans le graphe connexe G représenté ci-dessous, on a affecté à chaque arête une longueur, et on souhaite calculer le plus court chemin entre le sommet A et le sommet L. Pour cela on utilise l'algorithme suivant, appelé algorithme du plus court chemin.

On considère tous les sommets adjacents à A (ici, B, C et E), et on leur affecte une ``distance provisoire à A'', égale à la longueur de l'arête qui les relie à A. Parmi ceux-ci, le sommet le plus proche est C. On lui affecte comme ``distance définitive à A'' sa distance provisoire.

Puis on considère tous les sommets adjacents à C. On leur affecte comme distance provisoire à A la distance définitive de C à A plus la longueur de l'arête qui les relie à C. Ce faisant, il peut arriver que le même sommet se voit attribuées deux distances provisoires à A, une calculée à la première étape et une calculée à la deuxième. Dans ce cas, on conserve comme distance provisoire la plus petite des deux. Par exemple, la distance provisoire de E à A passe de 9 (première étape) à 8 (deuxième étape). Parmi tous les points possédant, à ce stade, une distance provisoire à A, le plus proche est B (la distance provisoire de B à A est 3, celle de E à A est 8, celle de F à A est 11). Aussi affecte-t-on à B la valeur 3 comme distance définitive à A.

L'étape suivante consistera donc à donner une distance provisoire à A à tous les sommets adjacents à B, à ne conserver éventuellement, lorsque deux distances provisoires sont attribuées au même point, que la plus petite des deux, à déterminer, parmi tous les points affectés d'une distance provisoire, le plus proche de A et à rendre cette distance définitive.

On continue jusquà ce que tous les points de G aient ``reçu leur distance définitive''. Celle-ci détermine alors la longueur du plus court chemin entre eux et A, et il ne reste plus qu'à préciser, parmi tous les chemins qui les relient à A, quel est ce plus court chemin.

(a) Poursuivre l'algorithme pour le graphe G : on indiquera, à chaque étape, la liste des distances provisoires à A et le nouveau point pour lequel on connaît la distance définitive à A.

(b) Quelle est la longueur du plus court chemin de A à L et quel est ce plus court chemin?