Mathématiques 2: Géométrie
Les graphes
L'optimisation par les graphes
Le chemin le plus court
1. Définition
Le chemin le plus court est celui qui correspond à la plus
petite valeur en kilomètres ou en heures de trajet entre un
point de départ et un point d'arrivé.
2. Méthode
Voici la procédure générale utilisée:
• On choisit un point de départ. Par exemple le point O,
• On considère TOUS les sommets adjacents,
• On retient la valeur le plus petite de l'arête,
ce qui donne alors le premier point intermédiaire,
• On élimine les arêtes adjacentes à ce point
qui forment le trajet le plus long vers ce point,
• On évalue les trajets qui restent
jusqu'au point d'arrivée,
• Le trajet le plus court est la solution finale.
3. Exemple
Quel est le chemin le plus court d'Ottawa à Portland ?
Voici le graphe des trajets:
Quel est le chemin le plus court du point
de départ O au point d'arrivée P ?
Trois valeurs sont possibles à partir du point O. Le point
adjacent le plus proche est S , OS = 348
À partir de O, le deuxième trajet pour arriver
à S est AQS de valeur441 + 230 = 671, AQS = 671 .
Il est plus grand que OS. Donc le trajet
QS est éliminé.