Kürzeste Wege
Eine der häufigsten Anwendungen von Graphen im Alltag ist die Darstellung von Infrastruktur- und Kommunikationsnetzen. Man denke beispielsweise an Straßenkarten, Buslinienpläne oder Flugverbindungen, all diese Dinge können durch Graphen repräsentiert werden.
Die Frage nach einem Weg zwischen zwei gegebenen Knoten in solchen Graphen ist eine besonders wichtige Anwendung. Meistens geht es dabei um ‘kostengünstige’ Wege, wobei ‘kostengünstig’ durchaus verschiedene Bedeutungen haben kann. Vielleicht such man nach dem kürzesten oder schnellsten Weg, vielleicht nach dem mit dem geringsten Energieverbrauch, den geringsten Reisekosten oder auch dem, der am wenigsten Geschwindigkeitskontrollen enthält.
A*-Algorithmus
Der A*-Algorithmus (sprich ‘A Stern’) arbeitet ähnlich wie der Dijkstra-Algorithmus. Zusätzlich wird aber noch eine Abschätzung für die Distanz zwischen Knoten verwendet, der Algorithmus wird so in vielen Fällen beschleunigt.
Algorithmus von Dijkstra
Der Algorithmus von Dijkstra berechnet einen kürzesten Weg zwischen zwei beliebigen Knoten, falls alle Kantengewichte im Graphen nichtnegativ sind.
Bellman-Ford-Algorithmus
Im Gegensatz zum A*-Algorithmus und dem Algorithmus von Dijkstra kann der Bellman-Ford-Algorithmus auch dann eingesetzt werden, wenn der Graph negative Kantengewichte enthält.
Floyd-Warshall-Algorithmus
Mit dem Floyd-Warshall-Algorithmus bestimmt man kürzeste Wege zwischen allen Knotenpaaren im Graphen. Der Algorithmus funktioniert selbst dann, wenn der Graph negative Kantengewichte enthält.
