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.