Dijkstra-Algorithmus

Gegeben ist eine Menge von Städten mit den entsprechenden Verbindungswegen. Gesucht ist der kürzeste Weg zwischen einer Stadt s und den übrigen Städten. Aus graphentheoretischer Sicht bedeutet dies in einem ungerichtetem Distanzgraphen die Berechnung kürzester Wege von einem Startknoten s zu allen anderen Knoten. Ein kürzester Weg von einem Start- zu einem Zielknoten bedeutet hier, daß die Summe der Kantenlängen vom Start- zum Zielknoten minimal ist. Ausgehend von s werden die kürzesten Wege für die Knoten mit aufsteigendem Abstand nacheinander bestimmt. Zuerst wird aus den Knoten, die mit s durch eine Kante verbunden sind, der Knoten v mit dem kürzesten Abstand zu s ausgewählt. Aus den gewählten Knoten (hier s und v) werden die sogenannten Randknoten bestimmt. Dies sind Knoten zu denen es einen Weg nach s über die gewählten Knoten gibt. D.h. von einem Randknoten gibt es eine Kante zu einem gewählten Knoten. Durch Neubestimmung der Randknoten ist es dann möglich, iterativ so fortzufahren, bis für jeden Knoten ein kürzester Weg nach s gefunden wurde. (Vorausgesetzt es gibt für jeden Knoten einen Weg zu s).