Mathématiques 514

Chemin le plus court

Le chemin le plus court consiste à obtenir la valeur la plus petite entre le point de départ et le point d'arrivé.  Il faut analyser tous les sommets mais ce n'est pas nécessaire que tous les sommets soient inclus dans la solution finale.

Par exemple, prenons le graphe suivant:

Supposons que l'on veut trouver le chemin le plus court entre A et D.

Soulignons les trois valeurs possibles à partir du sommet A.  Commençons par regarder le voisin ayant la plus petite valeur.  Dans ce cas-ci, c'est le sommet B.  Marquons la valeur 8 près du sommet B.  Cela donne

Maintenant, à partir du sommet B, regardons la valeurs des autres chemins. Vers le sommet C nous avons 8+12=20 et vers le sommet D nous obtenons 8+31=39.  Écrivons ces deux valeurs sur les arcs et soulignons-les.  Comme 20 est la plus petite valeur, nous allons analyser le sommet C.  L'arête qui mène de A à C vaut 17.  Donc, comme 17 est plus petit que 20, nous allons laisser tomber le trajet A-B-C.  Nous aurons 17 comme nouvelle valeur au sommet C.

Maintenant, considérons toutes les valeurs possibles qui mènent au sommet D. À partir de A nous avons 38.  À partir de B nous avons 39 et à partir de C nous avons 17+20=37.

La plus petite valeur étant 37, nous avons trouvé le chemin le plus court qui est A-C-D avec une valeur de 37.

Dernière mise à jour effectuée le 23 décembre 2005