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

MathématiquesEnsembles, logique et graphes16–17 ans

Une carte de lieux est modélisée par un graphe : les sommets sont des lieux, les arêtes des routes, et les poids des distances en kilomètres. Choisissez un sommet de départ et un sommet d'arrivée, puis déroulez pas à pas l'algorithme de Dijkstra : attribuez des étiquettes provisoires, fixez le sommet de plus petite étiquette et mettez à jour ses voisins. Cliquez sur une arête pour changer sa longueur (déviation ou route fermée) et voyez le plus court chemin changer, ainsi que les degrés des sommets et la condition d'existence d'un cycle eulérien.