Rentré de vacances, Romain veut partir de Chateauvillain (Haute-Marne) pour aller visiter le mémorial Charles de Gaule à Colombey-les-deux-églises à vélo.Pour cela il regarde une carte et se demande quel itinéraire il doit prendre afin de faire le moins de kilomètres possibles et d'arriver le plus vite possible...
Afin de ne pas oublier de question, vous pouvez télécharger ce fichier au format docx ou pdf
Distance et temps moyen entre communes
A votre avis quel est l'itinéraire le plus court ? Le plus rapide ?
La suite de cette activité consiste à mettre en évidence des méthodes pour confirmer ou infirmer ce que vous présentez.
Sur notre exemple les routes lient les villages entre eux.En algorithmique l'objet permettant de représenter cette situation est un graphe où les villages sont des noeuds et les routes des arêtes (ou éventuellement des arcs en cas de route à sens unique).
Recopier ou imprimer ce graphe où ne figurent que les noeuds (les villages) et complétez leur en rajoutant les arêtes (routes) manquantes entre les villages et en indiquant dessus la longueur de l'arête en km et le temps de parcours de l'arête en minutes.
On va utiliser le graphe trouvé précédemment pour essayer de trouver meilleur itinéraire possible : soit le plus court en distance, soit le
plus court en temps. Il existe plusieurs algorithmes permettant de calculer le meilleur itinéraire. Un des plus connus est l'algorithme de
On va maintenant résoudre notre algorithme selon l'algorithme de Dijkstra. Compléter le tableau suivant pour déterminer quel est l'itinéraire le plus court.
| Chateauvillain | Cirfontaines | Orges | Bricon | Autreville | Braux | Maranville | Lavilleneuve | Juzennecourt | Colombey |
|---|---|---|---|---|---|---|---|---|---|
| 0 | |||||||||
| X | 9,6-A | 6,6-A | 7,2-A | ||||||
| X | 9,6-A | 6,6-A | ... |
En déduire l'itinéraire le plus court pour aller de Chateauvillain à Colombey.
Refaire complètement le tableau en tenant compte cette fois ci de la durée de parcours. Le résultat obtenu est-il le même ?
Rentrer une à une les arêtes joignant les communes en leur donnant un poids (weight) égal à la distance entre les villages. (Attention le séparateur décimal est le point !)
Essayer de faire tourner ce programme dans edupython ou winpython. En déduire le trajet le plus court pour aller de Chateauvillain à Colombey et la distance parcourue.
Modifier ce programme pour que le poids des arêtes tiennent compte du temps nécessaire pour passer d'un village à l'autre. Le résultat obtenu est-il le même ?