Der Dijkstra-Algorithmus zur Berechnung kürzester Wege in Graphen

Vorgehen bei der Implementierung des Algorithmus, mögliche Fehlerquellen, Datenstrukturänderungen, Beobachtungen zur Laufzeit

Hausarbeit , 2009 , 18 Seiten , Note: 1,0

Informatik - Programmierung

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 Ausarbeitung beschreibt die Implementierung des Dijkstra-Algorithmus zur Berechnung kürzester Pfade in einem Graphen. Die Arbeit behandelt die Herausforderungen bei der Wahl geeigneter Datenstrukturen, die Implementierung des Algorithmus selbst sowie die Optimierung des Programms durch die Verwendung von Buckets.

• Datenstrukturen zur Verwaltung von Graphen und Front
• Implementierung des Dijkstra-Algorithmus
• Optimierung des Algorithmus durch Buckets
• Exception Handling
• Laufzeitmessung und -analyse

Zusammenfassung der Kapitel

Das erste Kapitel behandelt die Herangehensweise an die Implementierung des Dijkstra-Algorithmus. Es werden die gewählten Datenstrukturen für die Speicherung des Graphen und die Verwaltung der Front erläutert, wobei die Schwierigkeiten bei der Implementierung einer verketteten Liste im Detail beschrieben werden. Die Struktur des Programms wird vorgestellt, wobei die einzelnen Klassen und ihre Funktionen detailliert dargestellt werden. Abschließend werden Fehler und Beobachtungen während der Entwicklung des Programms diskutiert.

Das zweite Kapitel beschreibt die Anpassung des Programms für die Verwendung von Buckets. Es werden die Änderungen an den Klassen Ausgabe, Dijkstra, Graph und die Einführung der Klasse Buckets erläutert. Die Laufzeiten des Programms mit und ohne Buckets werden verglichen und die Vorteile der Bucket-Implementierung hervorgehoben. Abschließend werden Fehler und Beobachtungen sowie das Exception Handling behandelt.

Schlüsselwörter

Die Schlüsselwörter und Schwerpunktthemen des Textes umfassen den Dijkstra-Algorithmus, die kürzeste Pfadsuche, Graphen, Datenstrukturen, verkettete Listen, Adjazenzmatrix, Buckets, Laufzeitmessung, Exception Handling und Programmierpraktikum.

• Hochschule: Universität zu Köln (Zentrum für Angewandte Informatik Köln)
• Veranstaltung: Programmierpraktikum
• Note: 1,0
• Autor: Alexander Esser (Autor:in)
• Erscheinungsjahr: 2009
• Seiten: 18
• Katalognummer: V133039
• ISBN (eBook): 9783640395323
• ISBN (Buch): 9783640395507
• Sprache: Deutsch
• Schlagworte: Dijkstra, Algorithmus, kürzeste, Wege, Implementieren, Java, Programmieren, Praktikum, Programm, Struktur, Beobachtungen, Laufzeit, Datenstrukturänderung, Exception, Handling