Dijkstra-Algorithmus
Über diese App
Kürzeste Wege Schritt für Schritt: eigenen gewichteten Graphen bauen, Startknoten wählen und D-/R-Tabelle, MK-Menge und Pseudocode synchron mit der Knotenauswahl im Graphen mitverfolgen — vor und zurück navigierbar.
Wie Dijkstra kürzeste Wege findet
Der Algorithmus von Dijkstra berechnet in einem gewichteten Graphen die kürzesten Wege von einem Startknoten zu allen anderen Knoten. Voraussetzung ist, dass alle Kantengewichte nicht negativ sind. D[i] speichert die beste bisher bekannte Distanz zu Knoten i, anfangs ∞ außer D[Start] = 0. R[i] merkt sich den Vorgänger auf diesem Weg, daraus lässt sich der Pfad rekonstruieren. In jedem Schritt wird der Kandidat h mit kleinstem D[h] gewählt, seine Nachbarn werden geprüft (Relaxation) und h ist danach endgültig. Mit einem Min-Heap beträgt die Laufzeit O((|E| + |V|)·log|V|).
Was die App zeigt
Du baust einen gerichteten Graphen selbst: Knoten anlegen, zwei Knoten nacheinander anklicken für eine Kante, Gewichte ändern, Kanten oder Knoten löschen und Knoten frei verschieben. Nach Wahl des Startknotens läuft der Algorithmus schrittweise. Synchron dazu siehst du die Tabelle mit D- und R-Werten, die Kandidatenmenge MK und den Pseudocode mit dem aktuellen Schritt. Jeder Schritt wird in Worten erklärt, etwa ob eine Kante die Distanz verbessert oder nicht.
Selbst ausprobieren
Geh mit „Weiter“ und „Zurück“ durch den Lauf und beobachte, wann ein D-Wert sinkt und welcher Knoten als Nächstes gewählt wird. Baue einen Umweg, der mehr Kanten hat, aber kürzer ist, und prüfe, ob Dijkstra ihn findet. Lies am Ende über die R-Werte den kürzesten Pfad rückwärts ab. Am Ende ist MK leer und alle Distanzen vom Start sind endgültig.
Häufige Fragen
- Wie funktioniert der Dijkstra-Algorithmus?
- Er startet mit Distanz 0 am Startknoten und ∞ überall sonst. Wiederholt wird der noch offene Knoten mit kleinster Distanz gewählt und seine ausgehenden Kanten werden geprüft: Ist der Weg über ihn kürzer, wird die Distanz des Nachbarn aktualisiert. Danach ist dieser Knoten endgültig.
- Warum funktioniert Dijkstra nicht mit negativen Kantengewichten?
- Dijkstra erklärt einen Knoten für endgültig, sobald er die kleinste offene Distanz hat. Mit negativen Gewichten könnte ein späterer Umweg diese Distanz noch verkleinern. Für solche Graphen nutzt man zum Beispiel den Bellman-Ford-Algorithmus.
- Welche Laufzeit hat der Dijkstra-Algorithmus?
- Mit einer Prioritätswarteschlange als Min-Heap O((|E| + |V|)·log|V|). Die einfache Variante, die das Minimum linear sucht, braucht O(|V|²) und ist bei dichten Graphen oft ebenfalls praktikabel.
- Kann ich in der App einen eigenen Graphen bauen?
- Ja. Du legst Knoten und gerichtete Kanten an, änderst Gewichte, löschst Elemente und verschiebst Knoten. Danach wählst du den Startknoten und gehst den Algorithmus vor und zurück durch.
Fach: Lineare Probleme
Mehr aus Lineare Probleme
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps