Graphe d'un réseau routier
Un réseau de villes et les routes qui les relient peuvent être représentés par un graphe. Le temps de trajet (exprimé en minute) est alors indiqué sur l'arête (lien) entre deux villes.
Fondamental :
L'algorithme simplifié suivant détermine un itinéraire en choisissant systématiquement la ville suivante (non choisie précédemment) la plus proche de la précédente. D'autres algorithmes plus
complexes et plus efficaces sont utilisés par les systèmes de cartographie, comme l'algorithme de Dijkstra qui recherche à chaque étape le meilleur prédécesseur.
Se placer dans la ville de départ
Tant que la ville d'arrivée n'est pas atteinte
Depuis la ville courante aller si possible dans la ville voisine (non déjà visitée) la plus proche
Méthode : Travail demandé
Appliquer l'algorithme de recherche d'itinéraire de Brive à Millau puis de Millau à Brive.
Cet algorithme donne-t-il l'itinéraire le plus court ? Pourquoi ?
