Aus den Steinen, die Dir in den Weg gelegt werden, kannst du etwas Schönes bauen - Erich Kästner
Überblick
Jeder kennt das Problem, wie kommen wir auf dem schnellsten Weg in den Urlaub, nach Hause oder zu einem anderen Ziel. Ob mit dem Auto, der Bahn oder mit dem Fahrrad, die Auswahl der geeigneten Strecke wird meistens durch die Intuition oder den Blick auf eine Karte bestimmt. Aber auch hier kann der Computer uns helfen. Im Internet gibt es zahlreiche Routenplaner, meist liegen diese auch Atlanten bei oder wir können sie in der Bibliothek ausleihen. Natürlich können wir uns auch einen aktuellen Routenplaner kaufen. Bei der Beförderung von Paketen oder Briefen taucht ein ähnliches Problem auf, wie können wir möglichst kostengünstig die Post von A nach B befördern? Was für eine Technologie steckt also hinter der gesamten Problematik der kürzesten Wege? Wie können wir einfach und effizient einen kürzesten, schnellsten oder kostengünstigsten Weg von einem Start- zu einem oder mehreren Zielpunkten finden? Zur einfachen Darstellung des Problems benutzen wir die Sprache der Graphentheorie (siehe Ausarbeitung). Auf dieser Basis wollen wir uns die Algorithmen zur Berechnung der kürzesten Wege verdeutlichen und anhand von Beispielen aufzeigen (siehe Abschnitt 5 der Ausarbeitung). Im weiteren Teil der Diplomarbeit wollen wir aufzeigen, wie wir unser Tool Yet another Visualiser[15] entwickelt haben (siehe Kapitel III der Ausarbeitung). Ziel des Tools ist es, dem Benutzer die hier vorgestellten Graphalgorithmen zu veranschaulichen. Zum Abschluss möchten wir noch einen kleinen Ausblick auf Programmverbesserungen, weiterführende Theorie und andere Programme, die sich mit dem Thema Graphalgorithmen befassen, geben.
Graphendarstellung
Die Darstellung von Graphen im Dijkstra Algorithmus.
Datendarstellung
Datendarstellung als Adjazenzmatrix und Adjazenzliste in der Applikation.