Graphen werden häufig dazu eingesetzt, um Wege zu speichern und somit die Navigation erleichtern. Allerdings stellt sich dabei die Frage, wie findet man in einem Graphen den passenden beziehungsweise schnellsten Weg?

Würde man hier mit Backtracking vorgehen wäre das im Grunde genommen Brute-Force. Dabei ist allerdings kein Unterschied zwischen der Best- und Worst-Case Laufzeit festzustellen, da immer alle Wege abgesucht werden müssen. Daher verwendet man den Wegfindungsalgorithmus von Dijkstra, der deutlich effektiver nach dem schnellsten weg von einem Startknoten zu einem Zielknoten sucht.

Vorgehen

Grundlegend gehört der Dijkstra-Algorithmus zu der Klasse der Greedy-Algorithmen. Das bedeutet, dass er immer die aussichtsreichste Lösung bevorzugt.

Um nun mit der Suche anzufangen, werden zuerst die Abstände zu allen Knoten mit unendlich initialisiert, wobei der Abstand zum Startknoten mit 0 initialisiert wird.

Nachdem man den aktuellen Knoten markiert hat, betrachtet man nun alle Nachbarknoten beginnend bei dem mit dem geringsten Abstand. Wurde der aktuelle Nachbarknoten schon markiert, überspringt man diesen. Sonst wird der Gesamtabstand vom Startknoten bis zum aktuellen Nachbarknoten in diesem gespeichert.

Der unmarkierte Knoten mit dem bisherigen geringsten Abstand zum Startknoten wird nun als nächstes betrachtet, und das obige Verfahren wird wiederholt, bis alle möglichen Wege zum Zielknoten getestet wurden.

Dabei ist dieses Verfahren effektiver als beispielsweise Backtracking, da es während des Durchlaufes erkennt, wenn ein Knoten schneller über einen anderen Weg erreicht werden kann. Dafür wird ein Knoten nicht mehr weiter betrachtet, wenn er schon einen schnelleren Weg von einem anderen Knoten gespeichert hat.

Folgende Animation zeigt den Dijkstra-Algorithmus: