Anwendungen, Erweiterungen und Alternativen

Es gibt unterschiedliche Anwendungs- und Spezialfälle bei denen der Dijkstra Algorithmus Anwendung findet. Neben der Routenplanung als klassische Disziplin kann die Distanzberechnung auch in Bereichen genutzt werden, die nicht etwa euklidische Distanzen, sondern Zeit oder Kosten zur Grundlage haben. Zu den Spezialanwendungen des Algorithmus von Dijkstra gehören z.B. auch:

• Routing in Computernetzwerken

Zusätzlich zur Gewichtung der Kanten können auch auch Gewichte für Knoten festgelegt werden. Dies könnte beispielsweise der Fall sein, wenn der Umsteigevorgang innerhalb des Knotens "Hauptbahnhof" mit einem hohen Aufwand verbunden ist. In diesem Falle erhält der Knoten eine eigene Gewichtung, die dann in der Berechnung der kürzesten Wege berücksichtigt werden muss.

Der Dijkstra Algorithmus funktioniert nicht mit negativen Kantengewichtungen. Soll dennoch eine Shortest-Path-Berechnung durchgeführt werden, müssen andere Algorithmen zum Einsatz, wie etwa der Bellman-Ford-Algorthmus.

Der Algorithmus von Dijkstra ist nicht für alle Anwendungsfälle und Graphentypen geeignet. Weitere Algorithmen sind z.B. der Algorithmus von Kruskal oder der Algorithmus von Borůvka zur Berechnung minimaler Spannbäume in ungerichteten Graphen.