Diplomarbeit Home

Theorie und JAVA-Realisierung ausgewählter Algorithmen zur Bestimmung kürzester Wege in Graphen

Diplomarbeit im Studiengang Informatik der Fachhochschule Dortmund

von Robin Quast

Dortmund, den 12. Mai 2004
Betreuer: Prof. Dr. Burkhard Lenze

Ü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¨uhrende Theorie und andere Programme, die sich mit dem Thema Graphalgorithmen befassen, geben.

Screenshots
So hier nun noch 2 Bilder des Programms. Oben ist die Berechnung eines kürzesten Weges zu sehen. Unten die Ansicht der Ajazenzliste und -matrix.



 © Robin Quastwww.robinquast.de