Der Algorithmus von Dijkstra ist ein Greedy-Algorithmus. Er bestimmt den kürzesten Pfad innerhalb eines Graphens von einem Startknoten zu entweder einem seiner Knoten oder allen seiner Knoten. Eine Einschränkung dieses Algorithmusses ist, dass er auf Graphen mit negativen Kantengewichten nicht anwendbar ist.
Der Algorithmus ist beispielsweise auf
Wikipedia nachzulesen.
Beweis der Korrektheit
Hinweis: Beim Dijkstra können wir gut eine Priorityqueue verwenden, um die Menge der noch nicht fixierten Knoten zu verwalten.
Startknoten ist der Knoten
. Wir haben eine Menge
, in welcher die Knoten enthalten sind, für die der kürzeste Weg von
aus schon bestimmt ist
2
Von einem Knoten
dessen Abstand von
ist, können wir einen Knoten
, welcher noch nicht in der Menge
enthalten ist, mit den minimalsten Kosten von
erreichen. Wir wählen diesen Knoten. Formalisiert gilt für alle Paare
und
Würden wir nun einen Knoten
wählen, so würde gelten
Wenn
ist
größer als
, da
schon am kleinsten ist, weil in der Menge
schon alle kürzesten Pfade bestimmt sind.
Es ist unmöglich, daß
, da so der Weg
garantiert größer ist, da über einen anderen Knoten aus
gegangen werden muß und
minimal ist.
Fußnoten
- ... ist2
- Diese Menge können wir nach und nach herstellen. Wir starten dabei mit der leeren Menge, weil der Knoten selbst mit der Weglänge erreichbar ist und dies garantiert auch der kürzeste Weg ist.