Kürzeste Wege berechnen: Dijkstra-Algorithmus mit Tabelle

So benutzt du den Rechner

Schreibe jede Verbindung in eine eigene Zeile: zwei Knoten und die Länge, zum Beispiel A B 4 oder Köln Bonn 30. Gib Start und Ziel an und wähle, ob die Verbindungen in beide Richtungen gelten oder nur in eine, wie bei Einbahnstraßen. Der Rechner zeigt den kürzesten Weg, die Entfernungen zu allen Knoten und den Ablauf des Algorithmus.

So arbeitet der Dijkstra-Algorithmus

Am Anfang hat nur der Start die Entfernung 0, alle anderen Knoten bekommen vorläufig „unendlich“. Dann wiederholt man drei Schritte:

1. Wähle unter den noch nicht fertigen Knoten den mit der kleinsten vorläufigen Entfernung und markiere ihn als fertig.
2. Prüfe für jeden Nachbarn, ob der Weg über diesen Knoten kürzer ist als die bisher bekannte Entfernung. Wenn ja, verbessere sie und merke dir den Vorgänger.
3. Höre auf, sobald das Ziel fertig ist. Den Weg liest man rückwärts über die Vorgänger ab.

Ein Beispiel

Im voreingestellten Netz gibt es die Verbindungen A–B (4), A–C (2), B–C (5), B–D (10), C–E (3), E–D (4) und D–F (11). Von A aus wird zuerst C fertig (2), dann B (4), dann E über C (5), dann D über E (9) und zuletzt F über D (20). Der kürzeste Weg ist A → C → E → D → F mit der Länge 20. Der direkte Weg über B nach D wäre mit 14 bis D länger als der Umweg über C und E.

Eulerwege nebenbei

Der Rechner zählt auch, wie viele Kanten an jedem Knoten enden, den Grad. Daran sieht man, ob sich der Graph in einem Zug durchlaufen lässt, ohne eine Kante zweimal zu benutzen: Das geht genau dann, wenn höchstens zwei Knoten einen ungeraden Grad haben. Diese Regel fand Leonhard Euler 1736 am Königsberger Brückenproblem, dem Anfang der Graphentheorie. Im Beispiel haben vier Knoten einen ungeraden Grad, ein solcher Weg ist also unmöglich.

Knoten, Kanten, Grade und Eulerwege erklärt die Lernseite Graphentheorie. Wie Graphen bei der Färbung von Landkarten helfen, erzählt der Beitrag über den Vierfarbensatz.

Häufige Fragen