Optimisation    
 
  Graphes résume   
 
  Euler & Hamilton   
 
  Algorithme & heuristique   
 
  Units   
 
  home  
 
  ask us  
 

 

Mathématiques
2







© The scientific sentence. 2010


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é.

Il reste à évaluer OQP, OSP et OP :

OQP = 441 + 438 = 879
OSP = 348 + 278 = 626
OP = 642


OSP est le plus petit: C'est le chemin le plus court.

Le chemin le plus court d'ottawa à Portland est de 626 km, en passant par Sherbrooke.








  


chimie labs
|
Physics and Measurements
|
Probability & Statistics
|
Combinatorics - Probability
|
Chimie
|
Optics
|
contact
|


© Scientificsentence 2010. All rights reserved.