Ce que résout le panneau Shortest path Le panneau Shortest path exécute quatre algorithmes sur le même graphe pondéré : Dijkstra, A*, Bellman–Ford et Floyd–Warshall. Chaque ensemble de lignes nomme sa méthode, imprime la distance et la route et — pour les deux recherches à source unique qui tracent — l'ordre de stabilisation dans lequel les sommets ont été finalisés. Les graphes se construisent dans l'atelier de théorie des graphes partagé ; le commutateur Directed, les poids d'arêtes et la zone de collage de la matrice d'adjacence s'appliquent tous.
Comment exécuter chaque algorithme 01 Chargez un graphe et fixez les extrémités. Construisez un préréglage ou collez une matrice d'adjacence, puis choisissez Source et Target ; une construction par préréglage les réinitialise au premier et au dernier nœud. 02 Dijkstra répond distance, chemin et ordre de stabilisation, et refuse tout graphe avec une arête négative — l'erreur nomme l'arête et renvoie à Bellman–Ford. 03 A\ ajoute un sélecteur d'heuristique (manhattan / euclidean / zero) et rapporte les nœuds développés par rapport à Dijkstra, l'échelle d'heuristique réellement utilisée et si l'heuristique est consistante, donc optimale. 04 Bellman–Ford rapporte les tours de relaxation, liste les distances finales par nœud et signale un cycle négatif s'il en existe un. 05 Floyd–Warshall remplit la matrice des distances depuis une source, marque les nœuds de cycle négatif et peut répondre à n'importe quelle paire source/cible via la même table.
Relevés calculés Lus dans le panneau :
Configuration
Relevé
Graphe par défaut à 6 nœuds, Dijkstra A → F
distance 13 ; chemin A → C → B → D → E → F ; ordre de stabilisation A → C → B → D → E → F ; d[B] 3 , d[C] 2 , d[D] 8 , d[E] 10
Grille 4 × 5, Dijkstra 1-1 → 4-5
distance 7 ; l'ordre de stabilisation liste les 20 nœuds ; chemin 1-1 → 1-2 → 2-2 → 3-2 → 3-3 → 3-4 → 3-5 → 4-5
Graphe par défaut, A* avec euclidean
distance 13 , même chemin ; nœuds développés 6 / Dijkstra 6 ; échelle d'heuristique 0.01346 ; consistante optimale Yes
Préréglage Negative weights, Bellman–Ford depuis S
3 tours de relaxation ; d[S] 0 , d[A] 3 , d[B] 5 , d[C] 0 , d[D] 3 ; cycle négatif None
Préréglage Negative weights, Floyd–Warshall S → D
distance 3 ; chemin S → B → A → C → D ; nœuds de cycle négatif None
Le d[C] = 2 de Dijkstra vient de l'arête directe A–C, et d[B] = 3 de A → C → B, pas de l'arête plus lourde A–B de poids 4 . Bellman–Ford atteint les mêmes valeurs sur un graphe avec une arête −3, et Floyd–Warshall trouve S → B → A → C → D en enchaînant une arête négative et une positive.
Pourquoi A\* imprime une échelle Les coordonnées du canevas et les poids d'arêtes sont des grandeurs différentes, donc A* mesure l'heuristique sur la disposition et la met à l'échelle par le plus grand facteur qui maintient encore h(u) ≤ w(u,v) + h(v) sur chaque arc. Sur le graphe par défaut, l'échelle euclidean est 0.01346 , et les trois heuristiques développent les mêmes 6 nœuds que Dijkstra. La ligne consistante-optimale est la promesse que la distance renvoyée est exacte.
Limites
Poids non négatifs pour Dijkstra et A\*. Tous deux refusent une arête négative au lieu de renvoyer une distance trop grande ; basculez vers Bellman–Ford dans le même panneau pour le préréglage Negative weights. Une source par exécution. Pas de Dijkstra multi-source ni de Johnson tous-pairs ; Floyd–Warshall est l'option tous-pairs, à coût cubique. Le panneau ne lit pas non plus de listes d'arêtes depuis un fichier et n'exporte pas d'itinéraire — écrivez la matrice d'adjacence dans l'espace de travail et emportez-la vers les matrix tools , vers le panneau Spanning tree pour le câblage le moins cher ou vers Flow & matching pour les questions de capacité.
La frontière des arêtes négatives Construisez le préréglage Negative weights (S → A 4, S → B 5, A → C −3, B → A −2, B → C 4, C → D 3) et lancez Dijkstra avec Source S. Le panneau refuse avec le message "Edge 3 has weight -3. Dijkstra cannot handle negative weights (a settled distance could still be lowered) — use Bellman–Ford instead" plutôt qu'un nombre faux plausible. Passez l'algorithme à Bellman–Ford et S → C lit 0 , une distance que la stabilisation gloutonne de Dijkstra n'aurait jamais pu produire. A* porte le même refus ; son message renvoie lui aussi à Bellman–Ford.
Où cela sert Preuve d'optimalité pour une tournée L'ordre de stabilisation de Dijkstra est la preuve que les distances finales sont justes : chaque sommet est finalisé une fois et jamais revisité. Sur le graphe par défaut, l'arête directe A–B pèse 4 mais la route par C coûte 3 , et l'ordre A → C → B → D → E → F montre C finalisé avant B — le panneau expose son propre argument de correction.
Enseigner pourquoi les heuristiques doivent être mises à l'échelle Réglez A* sur l'heuristique zero et l'exécution est Dijkstra avec de la comptabilité (échelle 1 ) ; réglez euclidean sur le graphe par défaut disposé et l'échelle tombe à 0.01346 , donc l'estimation ne peut jamais dépasser le coût réel tandis que la route reste exacte.
Coûts négatifs en planification Le préréglage Negative weights modélise un crédit entre deux étapes. Bellman–Ford répond S → D en 3 ; Floyd–Warshall confirme la même valeur, et aucun ne signale de cycle négatif, donc la chaîne d'amélioration S → B → A → C → D se termine.
Confidentialité L'édition du graphe et chaque exécution de shortest path se font dans votre navigateur ; rien n'est téléversé.
Références
Wikipedia, Dijkstra's algorithm , en.wikipedia.org (访问日期:2026-10-07)— stabilisation gloutonne et poids non négatifs.
Wikipedia, Bellman–Ford algorithm , en.wikipedia.org (访问日期:2026-10-07)— tours de relaxation et détection de cycle négatif.
Wikipedia, Floyd–Warshall algorithm , en.wikipedia.org (访问日期:2026-10-07)— programmation dynamique tous-pairs.
Wikipedia, A* search algorithm , en.wikipedia.org (访问日期:2026-10-07)— heuristiques admissibles et consistantes.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 4th ed., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— plus courts chemins à source unique.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07