Wie der Dijkstra-Algorithmus arbeitet
Der Algorithmus geht auf Edsger W. Dijkstra zurück, der ihn 1959 veröffentlichte. Er löst das Problem des kürzesten Weges von einem Startknoten zu allen anderen Knoten, sofern kein Kantengewicht negativ ist. Gewichte können Entfernungen, Fahrzeiten, Kosten oder Leitungsverzögerungen sein. Navigationsgeräte, Routingprotokolle wie OSPF und viele Planungsprogramme nutzen ihn oder eng verwandte Verfahren.
Zu Beginn hat der Startknoten die Distanz null, alle anderen gelten als unendlich weit entfernt. In jedem Schritt wählt das Verfahren den noch nicht abgeschlossenen Knoten mit der kleinsten vorläufigen Distanz, schließt ihn ab und prüft alle seine Nachbarn. Ist der Umweg über diesen Knoten kürzer als die bisher bekannte Distanz eines Nachbarn, wird sie verbessert und der Vorgänger gemerkt. Aus den Vorgängern setzt der Rechner am Ende den Pfad zusammen.
Sie tragen die Kanten zeilenweise ein, etwa „A B 4“ für eine Verbindung von A nach B mit dem Gewicht 4. Bei einem ungerichteten Graphen darf jede Kante in beide Richtungen benutzt werden, bei einem gerichteten nur vom ersten zum zweiten Knoten. Knoten, die vom Start aus nicht erreichbar sind, werden als solche gekennzeichnet.
Grenzen, Varianten und praktische Hinweise
Negative Gewichte sind für Dijkstra nicht zulässig, weil ein bereits abgeschlossener Knoten später nicht mehr verbessert wird. Für solche Graphen ist der Bellman-Ford-Algorithmus geeignet, der zusätzlich negative Kreise erkennt. Der Rechner weist negative Gewichte deshalb mit einer Meldung zurück.
Die einfache Umsetzung ohne Prioritätswarteschlange benötigt eine Laufzeit in der Größenordnung der Knotenzahl im Quadrat. Mit einem Binärheap sinkt der Aufwand bei dünn besetzten Graphen auf etwa (Knoten + Kanten) · log(Knoten). Für dieses Werkzeug mit höchstens 60 Knoten und 400 Kanten spielt der Unterschied keine Rolle.
Gibt es mehrere gleich kurze Wege, zeigt der Rechner einen davon. Welcher das ist, hängt von der Reihenfolge der Kanten in Ihrer Liste ab. Die Distanz selbst ist in jedem Fall eindeutig. Wenn Sie alle kürzesten Wege kennen möchten, vergleichen Sie die Distanzen der Zwischenknoten.
Für Prüfungsaufgaben empfiehlt es sich, die Tabelle der vorläufigen Distanzen Schritt für Schritt von Hand aufzuschreiben und das Ergebnis anschließend mit dem Rechner zu kontrollieren. Achten Sie auf Tippfehler in Knotennamen: „a“ und „A“ gelten als verschiedene Knoten.
Tipps und typische Fehler
Wege richtig modellieren.
- Gewichte: Nicht negativ.
- Richtung: Einbahnstraßen gerichtet.
- Namen: Groß und klein beachten.
- Prüfen: Erst von Hand.
Mehr zum Thema Zahlensysteme, Logik und Prüfziffern
Häufige Fragen
Darf ein Kantengewicht null sein?
Ja. Gewichte von null sind erlaubt, nur negative Gewichte nicht. Eine Kante mit Gewicht null verbindet zwei Knoten ohne zusätzliche Kosten.
Was bedeutet „nicht erreichbar“?
Es gibt keinen Weg vom Startknoten zu diesem Knoten. Bei gerichteten Graphen liegt das oft an einer Kante, die nur in die Gegenrichtung zeigt.
Wie gebe ich doppelte Verbindungen ein?
Mehrere Kanten zwischen denselben Knoten sind zulässig. Der Algorithmus nutzt automatisch die günstigste davon.
Wer hat den Algorithmus erfunden?
Der niederländische Informatiker Edsger W. Dijkstra, veröffentlicht 1959.
Funktioniert Dijkstra mit gerichteten Graphen?
Ja, Sie können die Kanten als gerichtet markieren.
- Dijkstra Algorithmus
- kürzester Weg Graph
- Dijkstra online
- kürzeste Pfade berechnen
- Graph Distanz berechnen
- Dijkstra Beispiel
Alle Berechnungen erfolgen direkt in Ihrem Browser, Ihre Eingaben werden nicht übertragen oder gespeichert. Die Ergebnisse sind Orientierungswerte ohne Gewähr und ersetzen keine steuerliche, rechtliche oder finanzielle Beratung. Die Erklärtexte auf dieser Seite wurden mit KI erstellt. Letzte inhaltliche Änderung dieser Seite: . Mehr dazu: So entstehen und prüfen wir die Rechner.