Kürzeste Wege

Eine der meistgenutzten Anwendungen von Graphen im Alltag ist die Darstellung von Verkehrs- und Kommunikationsnetzen. Die Übersichtskarte der deutschen Autobahnen im offiziellen Führer "Autobahn Service", die Bahnlinien eines Verkehrsverbundes oder das Streckennetze einer Fluggesellschaft werden stets durch Graphen dargestellt, ohne dass wir uns dessen überhaupt noch bewusst werden.

Es leuchtet daher unmittelbar ein, dass in diesem Zusammenhang das Studium von Wegen in den entsprechenden Graphen von größter Bedeutung ist. Insbesondere wird man sich für möglichst "günstige" Wege interessieren. Dabei kann "günstig" viele Interpretationen erfahren: Vielleicht ist ein kürzester oder ein schnellster Weg gesucht, vielleicht ein billigster, vielleicht auch einer, auf dem man möglichst selten eine Radarstreife der Polizei antrifft.

Wir beschäftigen uns mit drei verschiedenen Lösungsalgorithmen:

• Dijkstra - Algorithmus
• A* - Algorithmus
• Bellman-Ford - Algorithmus
• Floyd-Warshall - Algorithmus