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
- Anhang
- Beziehungen zwischen den Klassen
- Laufzeit
- Input-Dateien
- Bereitgestellte Input-Dateien
- Eigene Input-Dateien
- Abschnitte aus dem Quellcode
Zielsetzung und Themenschwerpunkte
Die Arbeit beschreibt die Implementierung des Dijkstra-Algorithmus zur Bestimmung des kürzesten Weges in einem Graphen im Rahmen eines Programmierpraktikums. Der Fokus liegt auf der praktischen Umsetzung, der Wahl geeigneter Datenstrukturen und der Bewältigung auftretender Probleme.
- Implementierung des Dijkstra-Algorithmus in Java
- Auswahl und Implementierung geeigneter Datenstrukturen (Adjazenzmatrix, verkettete Liste, ArrayList)
- Lösung von Problemen bei der Implementierung der Datenstrukturen und des Algorithmus
- Exception Handling
- Optimierung der Programmstruktur und Laufzeit
Zusammenfassung der Kapitel
Herangehensweise Aufgabe 1: Dieses Kapitel beschreibt die anfängliche Herangehensweise an die Implementierung des Dijkstra-Algorithmus. Die Autoren diskutieren die Wahl der Datenstrukturen für die Speicherung des Graphen (Adjazenzmatrix) und die Verwaltung der Prioritätswarteschlange (initiale Implementierung mit einer selbstgeschriebenen verketteten Liste, später Umstellung auf ArrayList aufgrund von Problemen mit Generics). Die Implementierung des Algorithmus selbst erfolgte zeilenweise, wobei die Methoden in den Klassen `Liste` und `Knoten` schrittweise umgesetzt wurden. Die Autoren betonen die Modularität des Designs, das den Austausch der Adjazenzmatrix durch eine andere Datenstruktur erleichtern sollte.
Struktur des Programms: Dieses Kapitel beschreibt die Klassenstruktur des implementierten Programms. Die Klasse `Ausgabe` kümmert sich um das Schreiben des Ergebnisses in eine Datei. Die Kernfunktionalität liegt in der Klasse `Dijkstra`, welche den Algorithmus selbst beinhaltet, inklusive der Laufzeitmessung. Die Klasse `Graph` liest die Eingabedaten ein und stellt die Adjazenzmatrix bereit. Die Klasse `Knoten` repräsentiert die Knoten des Graphen, inklusive ihrer Distanz zum Startknoten und des Vorgängerknotens. Die Klasse `Liste` (initial eine selbst implementierte verkettete Liste, später eine ArrayList) verwaltet die Prioritätswarteschlange. Die Beschreibung der einzelnen Klassen verdeutlicht die modulare Gestaltung des Programms.
Fehler und Beobachtungen: Dieses Kapitel beschreibt die Herausforderungen bei der Implementierung, insbesondere bei der Bestimmung des Minimums in der Prioritätswarteschlange. Die anfängliche Implementierung mit der verketteten Liste führte zu Problemen bei der korrekten Minimumsbestimmung, die durch die Umstellung auf eine ArrayList behoben wurden. Die Komplexität der Minimumsbestimmung wird ausführlich erklärt.
Schlüsselwörter
Dijkstra-Algorithmus, Graph, Adjazenzmatrix, verkettete Liste, ArrayList, Prioritätswarteschlange, Exception Handling, Java, Programmierpraktikum, Datenstrukturen, Algorithmen, Laufzeitmessung.
Häufig gestellte Fragen zur Programmierpraktikumsarbeit: Implementierung des Dijkstra-Algorithmus
Was ist der Inhalt dieser Arbeit?
Die Arbeit dokumentiert die Implementierung des Dijkstra-Algorithmus zur Bestimmung des kürzesten Weges in einem Graphen in Java. Sie beschreibt den Entwicklungsprozess, die verwendeten Datenstrukturen (Adjazenzmatrix, verkettete Liste, ArrayList), die Bewältigung von Problemen während der Implementierung und Optimierungen der Programmstruktur und Laufzeit. Der Fokus liegt auf der praktischen Umsetzung und der Wahl geeigneter Datenstrukturen.
Welche Datenstrukturen wurden verwendet?
Die Arbeit verwendet zunächst eine selbst implementierte verkettete Liste als Prioritätswarteschlange, wechselt aber später aufgrund von Problemen mit Generics auf eine ArrayList. Der Graph wird mittels einer Adjazenzmatrix repräsentiert. Die Wahl der Datenstrukturen und die damit verbundenen Herausforderungen werden detailliert beschrieben.
Welche Klassen wurden implementiert?
Das Programm besteht aus den Klassen `Ausgabe` (für die Ausgabe der Ergebnisse), `Dijkstra` (für die Implementierung des Algorithmus selbst), `Graph` (zum Einlesen der Eingabedaten und Bereitstellen der Adjazenzmatrix), `Knoten` (zur Repräsentation der Knoten im Graphen) und `Liste` (initiale verkettete Liste, später ArrayList für die Prioritätswarteschlange). Die Beziehungen zwischen den Klassen werden im Anhang veranschaulicht.
Welche Probleme traten während der Implementierung auf?
Ein zentrales Problem betraf die effiziente Bestimmung des Minimums in der Prioritätswarteschlange. Die anfängliche Implementierung mit der selbstgeschriebenen verketteten Liste erwies sich als fehleranfällig. Der Wechsel zu ArrayList behob dieses Problem. Weitere Herausforderungen und deren Lösungen werden im Kapitel "Fehler und Beobachtungen" detailliert beschrieben.
Wie ist die Programmstruktur aufgebaut?
Das Programm ist modular aufgebaut, um den Austausch der Adjazenzmatrix durch andere Datenstrukturen zu erleichtern. Die einzelnen Klassen sind klar definiert und ihre Funktionen werden detailliert erklärt. Die Kapitel "Struktur des Programms" und der Anhang veranschaulichen den Aufbau und die Beziehungen zwischen den Klassen.
Wie wurde die Laufzeit gemessen und optimiert?
Die Laufzeitmessung erfolgt innerhalb der Klasse `Dijkstra`. Optimierungen konzentrierten sich auf die Wahl der Datenstrukturen und die effiziente Implementierung des Algorithmus. Die Laufzeiten und Optimierungsstrategien werden im Kapitel "Herangehensweise Aufgabe 2" und im Anhang dokumentiert.
Welche Themen werden in der Arbeit behandelt?
Die Arbeit behandelt die Implementierung des Dijkstra-Algorithmus in Java, die Auswahl und Implementierung geeigneter Datenstrukturen, die Lösung von Problemen bei der Implementierung, Exception Handling und die Optimierung der Programmstruktur und Laufzeit.
Wo finde ich den Quellcode?
Ausschnitte des Quellcodes sind im Anhang zu finden. Der vollständige Quellcode ist, falls verfügbar, separat anzufragen.
Was ist das Ziel der Arbeit?
Das Ziel ist die praktische Implementierung des Dijkstra-Algorithmus und die Demonstration des Verständnisses von Algorithmen und Datenstrukturen im Kontext eines Programmierpraktikums.
- Arbeit zitieren
- Alexander Esser (Autor:in), 2009, Der Dijkstra-Algorithmus zur Berechnung kürzester Wege in Graphen, München, GRIN Verlag, https://www.grin.com/document/133039
