Algorithmus von Dijkstra

Der Algorithmus von Dijkstra, der von Edsger W. Dijkstra entwickelt wurde, findet einen günstigsten Pfad zu einem Knoten innerhalb eines Graphen. Mit günstig ist gemeint, dass die Länge zum Knoten die Kürzeste ist.

Dies kann zum Beispiel nützlich sein, wenn wir eine Openstreetmap Karte haben und einen kürzesten Weg zwischen zwei Punkten finden möchten. Wir erklären die Funktionsweise.

Zunächst schauen wir uns ein Beispiel an. Der folgende Graphausschnitt sei gegeben:

Wie wir sehen, gibt es unterschiedliche Längen, die von einem zum anderen Knoten führen (z. B. 30, 20, 15, etc…).

Wir möchten nun von A nach F gelangen und zwar über den kürzesten Weg. Dazu markieren wir den Anfangsknoten grün und alle ausgehenden Kanten rot. Die Knoten, die am roten Kantenende sind, machen wir gelb. Wir erhalten:

Nun wählen wir den kürzesten Pfad, der von A ausgeht. In diesem Fall ist das der Pfad mit der Nummer “20”. Den Knoten “B” markieren wir also grün und die ausgehenden Kanten wieder gelb.

Jetzt wird C grün gefärbt und der Pfad von C nach D wird rot.

Wie wir sehen, besteht jetzt der Pfad von A nach D doppelt, nämlich über A nach B nach D und A nach C nach D. Hier müssen wir berechnen, wie viel der Weg insgesamt gekostet hat. Von A nach D über C beträgt er 30 + 5 = 35 und von A nach D über B beträgt er 20 + 7 = 27. Da 27 kleiner als 35 ist, können wir den Weg von C nach D streichen.

Nun kommt der nächste Knoten dran, dies ist im diesem Fall D. Auch hier werden die augehenden Kanten rot markiert und der eingehende Knoten wird gelb markiert:

Hier passiert noch gar nichts, der nächste Knoten wird grün markiert, nämlich E.

Nun wird F wieder doppelt von D und E eingeschlossen. Hier haben wir die Länge von A nach F über B und D mit der Summe 20 + 7 + 15 = 42. Und von A nach F über B und E mit der Summe 20 + 7 + 18 = 45. Also kann der längere Weg gestrichen werden, dies ist die Kante von D nach F.

Nun bleibt noch der Endknoten zu markieren. Wir erhalten:

Der kürzeste Weg ist also A, B, E, F mit Kantenlänge 42. Wir überprüfen dies:

A, B, D, F hat Kosten 45.
A, C, D, F hat Kosten 53.

Somit scheint es zu stimmen. Wir wollen jetzt noch einen allgemeinen Algorithmus mittels Pseudocode bestimmen:

while Alle Knoten sind noch nicht grün:
  Gehe nacheinander alle Knoten durch;
  Färbe Knoten grün;
  Färbe ausgehende Kanten rot;
  Färbe die Knoten, die an ausgehenden Kanten enden, gelb;
  if ein Knoten von zwei weiteren grünen Knoten eingeschlossen ist:
    Streiche die Kante, die die längere ist;
  end if;
end while;

Den genaueren Pseudocode findet man unter Wikipedia -> Dijkstra Algorithmus .