Was das Panel Shortest path löst Das Panel Shortest path führt vier Algorithmen über denselben gewichteten Graphen aus: Dijkstra, A*, Bellman–Ford und Floyd–Warshall. Jede Zeilengruppe nennt ihr Verfahren, gibt Distanz und Route aus und — bei den beiden Single-Source-Suchen, die nachverfolgen — die Settle-Reihenfolge, in der die Knoten finalisiert wurden. Graphen werden in der gemeinsamen Graph-Theorie-Workbench gebaut; der Directed-Umschalter, Kantengewichte und das Einfügefeld für die Adjazenzmatrix gelten alle.
So führen Sie jeden Algorithmus aus 01 Einen Graphen laden und die Endpunkte setzen. Ein Preset bauen oder eine Adjazenzmatrix einfügen, dann Source und Target wählen; ein Preset-Build setzt sie auf den ersten und letzten Knoten zurück. 02 Dijkstra beantwortet Distanz, Pfad und Settle-Reihenfolge und verweigert jeden Graphen mit einer negativen Kante — der Fehler nennt die Kante und verweist auf Bellman–Ford. 03 A\ fügt einen Heuristik-Auswähler hinzu (manhattan / euclidean / zero) und meldet die expandierten Knoten im Vergleich zu Dijkstra, den tatsächlich verwendeten Heuristikmaßstab und ob die Heuristik konsistent und damit optimal ist. 04 Bellman–Ford meldet die Relaxationsrunden, listet die finalen Distanzen je Knoten und markiert einen negativen Zyklus, falls vorhanden. 05 Floyd–Warshall füllt die Distanzmatrix von einer Quelle, markiert Negativzyklus-Knoten und kann jedes Quelle-Ziel-Paar über dieselbe Tabelle beantworten.
Durchgerechnete Messwerte Aus dem Panel gelesen:
Setup
Messwert
Standardgraph mit 6 Knoten, Dijkstra A → F
Distanz 13 ; Pfad A → C → B → D → E → F ; Settle-Reihenfolge A → C → B → D → E → F ; d[B] 3 , d[C] 2 , d[D] 8 , d[E] 10
Gitter 4 × 5, Dijkstra 1-1 → 4-5
Distanz 7 ; Settle-Reihenfolge listet alle 20 Knoten; Pfad 1-1 → 1-2 → 2-2 → 3-2 → 3-3 → 3-4 → 3-5 → 4-5
Standardgraph, A* mit euclidean
Distanz 13 , derselbe Pfad; expandierte Knoten 6 / Dijkstra 6 ; Heuristikmaßstab 0.01346 ; konsistent optimal Yes
Preset Negative weights, Bellman–Ford von S
3 Relaxationsrunden; d[S] 0 , d[A] 3 , d[B] 5 , d[C] 0 , d[D] 3 ; negativer Zyklus None
Preset Negative weights, Floyd–Warshall S → D
Distanz 3 ; Pfad S → B → A → C → D ; Negativzyklus-Knoten None
Dijkstras d[C] = 2 stammt von der direkten Kante A–C, und d[B] = 3 von A → C → B, nicht von der schwereren Kante A–B mit Gewicht 4 . Bellman–Ford erreicht dieselben Werte auf einem Graphen mit einer −3-Kante, und Floyd–Warshall findet S → B → A → C → D durch die Verkettung einer negativen und einer positiven Kante.
Warum A\* einen Maßstab ausgibt Canvas-Koordinaten und Kantengewichte sind verschiedene Größen, also misst A* die Heuristik auf dem Layout und skaliert sie mit dem größten Faktor, der h(u) ≤ w(u,v) + h(v) auf jedem Bogen noch erhält. Im Standardgraphen beträgt der euclidean-Maßstab 0.01346 , und alle drei Heuristiken expandieren dieselben 6 Knoten wie Dijkstra. Die Zeile konsistent-optimal ist das Versprechen, dass die zurückgegebene Distanz exakt ist.
Grenzen
Nicht-negative Gewichte für Dijkstra und A\*. Beide verweigern eine negative Kante, statt eine zu große Distanz zurückzugeben; wechseln Sie im selben Panel zu Bellman–Ford für das Preset Negative weights. Eine Quelle pro Lauf. Es gibt keinen Multi-Source-Dijkstra und kein Johnson-All-Pairs; Floyd–Warshall ist die All-Pairs-Option zu kubischen Kosten. Das Panel liest auch keine Kantenlisten aus einer Datei und exportiert keine Route — schreiben Sie die Adjazenzmatrix in den Workspace und nehmen Sie sie mit zu den matrix tools , zum Panel Spanning tree für die günstigste Verkabelung oder zu Flow & matching für Kapazitätsfragen.
Die Negativkanten-Grenze Bauen Sie das Preset Negative weights (S → A 4, S → B 5, A → C −3, B → A −2, B → C 4, C → D 3) und drücken Sie Dijkstra mit Source S. Das Panel verweigert mit der Meldung "Edge 3 has weight -3. Dijkstra cannot handle negative weights (a settled distance could still be lowered) — use Bellman–Ford instead" statt einer plausiblen falschen Zahl. Wechseln Sie den Algorithmus zu Bellman–Ford, und S → C liest 0 , eine Distanz, die Dijkstras gieriges Settle nie hätte erzeugen können. A* trägt dieselbe Verweigerung; seine Meldung verweist ebenfalls auf Bellman–Ford.
Wo es nützlich ist Optimalitätsbeweis für eine Tour Dijkstras Settle-Reihenfolge ist der Beweis, dass die finalen Distanzen stimmen: Jeder Knoten wird genau einmal finalisiert und nie erneut besucht. Im Standardgraphen wiegt die direkte Kante A–B 4 , aber die Route über C kostet 3 , und die Reihenfolge A → C → B → D → E → F zeigt C vor B finalisiert — das Panel zeigt sein eigenes Korrektheitsargument.
Warum Heuristiken skaliert werden müssen, lehren Stellen Sie A* auf die Zero-Heuristik, und der Lauf ist Dijkstra mit Buchhaltung (Maßstab 1 ); stellen Sie euclidean im ausgelegten Standardgraphen ein, und der Maßstab fällt auf 0.01346 , sodass die Schätzung die wahren Kosten nie überschreiten kann, während die Route exakt bleibt.
Negative Kosten in der Planung Das Preset Negative weights modelliert ein Guthaben zwischen zwei Stufen. Bellman–Ford beantwortet S → D in 3 ; Floyd–Warshall bestätigt denselben Wert, und keiner meldet einen negativen Zyklus, sodass die Verbesserungskette S → B → A → C → D terminiert.
Datenschutz Graphbearbeitung und jeder Shortest-path-Lauf finden in Ihrem Browser statt; nichts wird hochgeladen.
Referenzen
Wikipedia, Dijkstra's algorithm , en.wikipedia.org (访问日期:2026-10-07)— gieriges Settle und nicht-negative Gewichte.
Wikipedia, Bellman–Ford algorithm , en.wikipedia.org (访问日期:2026-10-07)— Relaxationsrunden und Negativzyklus-Erkennung.
Wikipedia, Floyd–Warshall algorithm , en.wikipedia.org (访问日期:2026-10-07)— All-Pairs-Dynamikprogrammierung.
Wikipedia, A* search algorithm , en.wikipedia.org (访问日期:2026-10-07)— zulässige und konsistente Heuristiken.
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)— Single-Source-Kürzeste-Wege.
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