Im Rahmen des Programmierpraktikums an der Universität zu Köln implementierten wir zunächst in Gruppenarbeit den Dijkstra-Algorithmus zur Berechnung kürzester Wege in Java. In Einzelarbeit verfasste ich anschließend die schriftliche Ausarbeitung. In der Ausarbeitung wird unser Vorgehen beim Programmieren beschrieben, die Struktur des Programms wird ausführlich erläutert und es wird umfassend auf die Möglichkeit eingegangen, später die zugrunde liegende Datenstruktur abzuändern. Außerdem enthält die Ausarbeitung Hinweise auf mögliche Fehler sowie Beobachtungen zur Laufzeit und zum Exception Handling.
Inhaltsverzeichnis
Herangehensweise Aufgabe 1
Vom Blatt auf den Bildschirm
Struktur des Programms
Die Klasse Ausgabe
Die Klasse Dijkstra
Die Klasse Graph
Die Klasse Knoten
Die Klasse Liste
Fehler und Beobachtungen
Testdaten
Herangehensweise Aufgabe 2
Anpassung des ersten Programms / neue Struktur
Änderungen an der Klasse Ausgabe
Die Klasse Buckets
Änderungen an der Klasse Dijkstra
Das Interface Front
Änderungen an der Klasse Graph
Die Klasse Main
Laufzeiten
Fehler und Beobachtungen
Exception Handling
Fazit
Zielsetzung & Themen
Die vorliegende Ausarbeitung dokumentiert die Implementierung und Optimierung des Dijkstra-Algorithmus im Rahmen eines Programmierpraktikums, wobei der Fokus auf der strukturierten Programmierung in Java, dem effizienten Umgang mit Datenstrukturen und der Fehlerbehandlung liegt.
- Implementierung des Dijkstra-Algorithmus zur Berechnung kürzester Wege.
- Strukturierung komplexer Programme durch objektorientiertes Design (Klassen und Interfaces).
- Vergleich und Optimierung von Datenstrukturen (verkettete Listen vs. Buckets).
- Umgang mit Fehlerquellen (Exception Handling) bei der Datenverarbeitung.
- Praktische Erfahrung in der Gruppenarbeit und Einhaltung von Projektfristen.
Auszug aus dem Buch
Die Klasse Dijkstra
Die Klasse Dijkstra ist die wichtigste Klasse innerhalb unseres Programms. Sie dient der Berechnung der kürzesten Entfernung zwischen Start- und Zielknoten.
In Dijkstra werden zunächst die Knoten sowie eine Liste zur Verwaltung der Front initialisiert, anschließend wird der Dijkstra-Algorithmus ausgeführt: Bei jeder Iteration wird das Element u in der Front gesucht, dessen Distanz zum Startknoten minimal ist. Es werden alle Kanten (u, v) betrachtet, die von diesem Knoten ausgehen. Sollte man den Zielknoten kostengünstiger erreichen, indem man eine dieser Kanten verfolgt, so wird der neue Knoten v in die Front aufgenommen, die Distanz und der Vorgänger von v werden geändert, u wird aus der Front gelöscht. Diese Schleife wird solange durchlaufen, bis die Front keine Knoten mehr enthält. Dann entspricht die Distanz des Zielknotens der Länge des kürzesten Weges oder es wurde kein Weg zum Zielknoten gefunden.
Neben der Länge des kürzesten Weges wird in Dijkstra auch die Laufzeit des Programms berechnet, indem zu Beginn und nach dem Ausführen des Algorithmus die Systemzeit gemessen wird. Auch der Aufruf des Programms erfolgte in Aufgabe 1 noch in der main()-Methode der Klasse Dijkstra.
Zusammenfassung der Kapitel
Herangehensweise Aufgabe 1: Dokumentation der ersten Implementierung des Dijkstra-Algorithmus unter Verwendung einer verketteten Liste für die Knotenverwaltung.
Herangehensweise Aufgabe 2: Beschreibung der strukturellen Anpassungen, insbesondere der Einführung von Buckets als alternative Datenstruktur und der Nutzung eines Front-Interfaces zur Flexibilisierung.
Fazit: Reflexion über die gewonnenen Erkenntnisse bezüglich Java-Generics, objektorientierter Gruppenarbeit und dem praktischen Umgang mit starren Terminvorgaben.
Schlüsselwörter
Dijkstra-Algorithmus, Java, Programmierung, Datenstrukturen, ArrayList, verkettete Liste, Buckets, Laufzeit, Optimierung, Exception Handling, Graph, Knoten, Kanten, Implementierung, Objektorientierung
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die praktische Umsetzung und stufenweise Optimierung des Dijkstra-Algorithmus in der Programmiersprache Java.
Welche zentralen Themenfelder werden abgedeckt?
Die Schwerpunkte liegen auf der algorithmischen Realisierung, der Wahl geeigneter Datenstrukturen zur effizienten Verwaltung der Knotenfront sowie der robusten Fehlerbehandlung.
Was war das primäre Ziel der Arbeit?
Ziel war es, kürzeste Wege in einem Graphen effizient zu berechnen und dabei ein Programm zu entwickeln, das durch eine klare Klassenstruktur gut wartbar und erweiterbar ist.
Welche wissenschaftlichen Methoden wurden verwendet?
Es wurde eine iterative Entwicklungsmethode gewählt, bei der Konzepte aus der theoretischen Informatik in Java-Code übersetzt und durch Laufzeitmessungen sowie Fehleranalysen validiert wurden.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die erste Implementierungsphase, die strukturelle Überarbeitung durch neue Datenstrukturen wie Buckets sowie eine detaillierte Auseinandersetzung mit auftretenden Fehlern und deren Behebung.
Welche Schlüsselwörter charakterisieren die Arbeit?
Dijkstra-Algorithmus, Datenstrukturen, Laufzeitoptimierung, Objektorientierung und Java-Programmierung sind die prägenden Begriffe.
Warum wurden in der zweiten Aufgabe Buckets eingeführt?
Die Buckets sollten theoretisch die Laufzeit verbessern, indem sie die Suche nach dem Minimum bei der Knotenverwaltung beschleunigen, was durch eine doppelt verschachtelte ArrayList umgesetzt wurde.
Welche Rolle spielt das Interface Front?
Das Interface dient dazu, die Datenstrukturen (Liste oder Buckets) zu vereinheitlichen, sodass der Dijkstra-Algorithmus ohne Code-Änderungen flexibel mit unterschiedlichen Backends betrieben werden kann.
Warum führten Bildschirmausgaben zu Performance-Problemen?
Das Schreiben von Text auf die Konsole ist ein vergleichsweise langsamer Vorgang, der die Rechenzeit bei großen Datenmengen signifikant in die Höhe trieb und die eigentliche Algorithmus-Laufzeit verfälschte.
- Quote paper
- Alexander Esser (Author), 2009, Der Dijkstra-Algorithmus zur Berechnung kürzester Wege in Graphen, Munich, GRIN Verlag, https://www.grin.com/document/133039
