Dijkstra-Algorithmus

Der Dijkstra-Algorithmus findet den kürzesten Pfad in einem Graphen mit nicht-negativen Kantengewichten. Er arbeitet gierig (greedy) und aktualisiert Pfade durch Relaxation: d(v) = min(d(v), d(u) + w(u,v)). Mit einer Fibonacci-Heap-Prioritätswarteschlange wird die Laufzeit auf O(E + V log V) optimiert.

Dijkstra lässt eine Front vom Startknoten nach außen wachsen und wählt stets den nächstgelegenen noch nicht besuchten Knoten aus. Da jedes Kantengewicht nicht-negativ ist, kann kein späterer Umweg eine bereits gefundene kürzere Strecke unterbieten — sobald ein Knoten festgelegt ist, ist seine Distanz endgültig und wird nie erneut geprüft. Deshalb verlassen sich Routenplaner und Internet-Routingprotokolle wie OSPF darauf, um zuverlässige kürzeste Wege zu berechnen.

Edsger Dijkstra ersann den Algorithmus 1956 in etwa zwanzig Minuten, ganz ohne Bleistift und Papier, während er sich auf der Terrasse eines Amsterdamer Cafés ausruhte. Er suchte ein Demonstrationsproblem für den Rechner ARMAC und wählte die kürzeste Route zwischen den niederländischen Städten Rotterdam und Groningen. Drei Jahre später veröffentlichte er ihn in einem kaum dreiseitigen Aufsatz — einem der meistzitierten Ergebnisse der Informatik.