Graphes pondérés et plus court chemin – algorithme de Dijkstra

Ce qu’elle montre

Un réseau routier se modélise par un graphe pondéré : les sommets sont des lieux, les arêtes des routes et chaque poids une distance en kilomètres. L'algorithme de Dijkstra attribue à chaque sommet une étiquette provisoire de distance depuis le départ : à chaque étape, il fixe le sommet non fixé de plus petite étiquette et met à jour les étiquettes de ses voisins. Comme tous les poids sont positifs, une étiquette fixée ne peut plus être améliorée. La simulation affiche aussi les degrés des sommets, dont la somme vaut le double du nombre d'arêtes et qui, dans un graphe connexe, décident de l'existence de chaînes et de cycles eulériens.

Mode d’emploi

Choisissez une Carte, puis le départ et l'arrivée dans De et À. Appuyez plusieurs fois sur Étape suivante en demandant aux élèves de prévoir quel sommet sera fixé et quelles étiquettes vont changer ; utilisez Étape précédente pour revenir sur un choix. Comparez l'itinéraire obtenu avec celui qui emprunte le moins de routes. Réglez ensuite Clic sur arête sur fermer / ouvrir, fermez une route du plus court chemin et appuyez sur Tout exécuter pour voir le nouvel itinéraire.

Paramètres modifiables

• Carte Ville (7 lieux), Communes d'une région (9 lieux)
• Sommet de départ
• Sommet d'arrivée

Questions à explorer

1. Pourquoi l'étiquette d'un sommet ne change-t-elle plus une fois qu'il est fixé ?
2. L'itinéraire comportant le moins d'arêtes est-il toujours le plus court ? Quel exemple de la carte le montre ?
3. Quelles routes pourriez-vous fermer pour que les routes restantes restent reliées et que le graphe possède un cycle eulérien ?