Dijkstra

Une arête par ligne : A B 4, ou A B pour un poids de 1. Séparez les valeurs par des espaces ou des virgules ; utilisez un point décimal pour les poids. Les lignes vides ou commençant par # sont ignorées. Limites : 30 nœuds, 100 arêtes, 12 caractères par nom et poids absolu de 10⁹. Les noms sont sensibles à la casse.

Trouver le chemin calcule immédiatement. Un pas affiche un événement ; Animer les parcourt au délai choisi. Pause conserve l’état. Modifier une entrée efface les anciens résultats. Réinitialiser restaure l’exemple. Quitter ou masquer l’outil arrête l’animation. Le texte du graphe, le départ, la cible, le sens, l’algorithme et le délai sont enregistrés localement, même les brouillons incomplets. Recharger restaure les entrées, pas la progression.

Dijkstra et A* exigent des poids non négatifs ; BFS accepte seulement le poids 1. Bellman-Ford accepte les poids négatifs, mais rejette tout cycle négatif accessible depuis le départ, même si la cible n’est pas concernée. Une arête négative non orientée crée un tel cycle. A* utilise le poids minimum multiplié par la distance en sauts calculée à rebours ; cette borne est cohérente. Si le minimum vaut 0, la recherche équivaut à Dijkstra.

L’exemple coûte 9 : A → C → E → F. Seul le chemin cible affiché est garanti définitif ; les autres distances peuvent rester provisoires. En cas d’égalité, un plus court chemin est choisi. Les positions circulaires sont schématiques. Les noms longs sont abrégés dans le dessin, mais restent complets dans le tableau et l’infobulle. Outil pédagogique pour petits graphes, pas un solveur de cartes ou de grands réseaux.