Kleines Nachschlagewerk Informatik
Wegsuche mit Dijkstra
Worum geht es?
Ziel des Dijkstra-Algorithmus ist es, den kürzesten Weg vom Start- zum Zielknoten zu finden.
Wie funktioniert die Wegsuche?
Ausgehend von Start werden alle Nachbarknoten untersucht. Zu jedem Knoten merkt man sich die Weglänge. Dann nimmt man den Knoten mit der kürzesten Entfernung und besucht wieder alle Nachbarknoten. Die Entfernungen werden aufaddiert. Erreicht man einen schon besuchten Knoten mit kürzerer Entfernung, merkt man sich diese.

Man nimmt also den zu jedem Zustand besten (kürzesten) Weg und besucht alle Nachbarknoten. Den Vorgänger merkt man sich, z.B. im Knotenobjekt. Hat man den Zielknoten erreicht, stoppt man und gewinnt den kürzesten Pfad, indem man sich von Vorgänger zu Vorgänger handelt.
Beispiel
In folgendem Graphen soll der kürzeste Weg von A nach H gefunden werden. Man geht vom aktuellen Punkt zu jedem angrenzenden Knoten und merkt sich die Entfernung und den Knoten, von dem man kam. Der bisher beste Weg wird dann beschritten. Kommt man später noch einmal auf kürzerem Weg zu einem bereits besuchten Knoten, korrigiert man die Entfernung.

Man hat also eine Menge von Wegen. Den jeweils kürzesten verfolgt man weiter. Sind alle Knoten besucht worden, stoppt man.



aktueller KnotenVorgängerzu Bzu Czu Dzu Ezu Fzu Gzu HBemerkung
A-123-----der kürzeste Weg führt nach C
CA12x5----der beste Weg führt nach D
DC8xx-1612-es wurde ein besserer Weg nach B gefunden
BDxxx121612-von B geht es nach E
EBxxxx1312-nun ist der kürzeste Weg der nach G
GDxxxx13x20am Ziel, aber noch sind Wege offen
FExxxxxx15der andere Weg erweist sich als besser
Als kürzester Weg ergibt sich - wenn man sich rückwärts durch die Vorgänger hangelt - H-F-E-B-D-C-A.



Der Algorithmus

      Für alle Knoten
          Markiere Knoten als unbesucht
          Trage als Entfernung einen sehr großen Wert ein
      aktuellerKnoten = startKnoten
      solange Knoten unbesucht sind
          für alle Nachbarknoten
              wenn Nachbarknoten unbesucht
                  d = Entfernung des aktuellen Knotens
                  n = Entfernung zu diesem NachbarKnoten
                  a = eingetragene Entfernung des Nachbarknotens
                  wenn d + n < a
                      Entfernung des Nachbarknotens = d+n
                      Vorgänger des Nachbarknotens = aktuellerKnoten
          aktuellerKnoten auf besucht setzen
          aktuellerKnoten = unbesuchter Knoten mit kürzester Entfernung
    
      Vom Zielknoten ausgehend alle Vorgänger ermitteln
            
Zur Beachtung
Dijkstra ist ein Greedy-Algorithmus. Er fängt also mit dem günstigsten an, weiß aber nicht, wie der restliche Weg weitergeht. Was anfänglich gut aussieht, kann sich als Sackgasse erweisen. Möchte man dies vermeiden, muss man den Weg zum Ziel abschätzen. In Graphen geht dies nicht. Legt man ein Raster darunter, kann man die Entfernung über die Luftlinie schätzen (siehe A-Star Algorithmus).

Der Algorithmus kann nicht enden, wenn man den Zielknoten erreicht hat. Sind noch Wege offen, kann durchaus ein kürzerer dabei sein.