Dijkstra

Eine Kante je Zeile eingeben: A B 4 oder A B für Gewicht 1. Leerzeichen oder Kommas trennen die Angaben; Gewichte verwenden den Dezimalpunkt. Leerzeilen und Zeilen mit # am Anfang werden ignoriert. Höchstens 30 Knoten, 100 Kanten, 12 Zeichen je Knoten und Gewichtsbetrag 10⁹. Groß- und Kleinschreibung der Knotennamen zählt.

Pfad finden rechnet sofort. Ein Schritt zeigt Initialisierung, Knoten- oder Kantenprüfung; Animieren folgt diesen Ereignissen mit der eingestellten Verzögerung. Pause behält den Zustand. Änderungen verwerfen alte Ergebnisse. Zurücksetzen stellt das Beispiel wieder her. Toolwechsel oder Ausblenden stoppt die Animation. Kantentext, Start, Ziel, Richtung, Algorithmus und Verzögerung bleiben lokal gespeichert, auch unfertige Eingaben. Reload stellt Eingaben wieder her, nicht den Suchfortschritt.

Dijkstra und A* benötigen nichtnegative Gewichte. BFS akzeptiert nur Gewicht 1. Bellman-Ford erlaubt negative Gewichte, verwirft aber jeden Lauf mit einem vom Start erreichbaren negativen Zyklus, auch wenn dieser das Ziel nicht betrifft. In ungerichteten Graphen bildet eine negative Kante bereits einen negativen Zyklus. A* verwendet kleinstes Kantengewicht mal rückwärts berechnete Hop-Distanz als konsistente Untergrenze; bei kleinstem Gewicht 0 entspricht die Suche Dijkstra.

Das Beispiel hat Kosten 9: A → C → E → F. Nur der ausgegebene Zielpfad ist garantiert endgültig; andere Tabellendistanzen können beim Erreichen des Ziels noch vorläufig sein. Bei Gleichstand erscheint ein kürzester Pfad. Die Kreispositionen sind schematisch und unabhängig von Gewichten. Lange Knotennamen werden im Bild gekürzt; Tabelle und Knoten-Tooltip zeigen sie vollständig. Das ist ein Lehrtool für kleine Graphen, kein Karten- oder Großnetzsolver.