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

Inhaltsverzeichnis

Herangehensweise Aufgabe 1
Vom Blatt auf den Bildschirm
Struktur des Programms
Die Klasse Ausgabe
Die Klasse Di / kstra
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 Di / kstra
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

1. Herangehensweise Aufgabe 1

1.1. Vom Blatt auf den Bildschirm

Datenstruktur zur Speicherung der Kantengewichte

Bevor wir begannen, den Dijkstra-Algorithmus zu implementieren, diskutierten wir zunächst, mithilfe welcher Datenstrukturen wir den Graphen und die Front verwalten wollen. Wir entschieden uns, die Kantengewichte in einer Adjazenzmatrix zu speichern, die wir durch ein zweidimensionales Array umsetzten.

Datenstruktur zur Verwaltung der Front

Die Front wollten wir mithilfe in einer verketteten Liste verwalten. Große Probleme bereitete uns jedoch die Implementierung dieser Liste. Generics waren uns anfangs noch nicht bekannt; wir konnten die Liste daher nicht durch Vektoren oder eine ArrayList implementieren. Hätte man beispielsweise mit dem Befehl

V.get(0).knotennummer

auf die Knotennummer des ersten Knotens, der im Vektor V gespeichert ist, zugreifen wollen, so hätte dies ohne Generics zu einer Fehlermeldung geführt, da nicht sichergestellt ist, dass das Element V.get(0) ein Knoten ist. Wir führten daraufhin lange Diskussionen, welche andere Datenstruktur wir zur Verwaltung der Front benutzen könnten oder wie wir die verkettete Liste anders implementieren könnten. Letztendlich schrieben wir eine eigene Klasse Liste, in der die verkettete Liste mit einem head -, naechster - und tail -Zeiger verwaltet wurde¹. Als uns Generics später bekannt waren, wandelten wir die Klasse Liste ab und verwendeten fortan eine ArrayList.

Implementierung des Dijkstra-Algorithmus

Nachdem wir die Schwierigkeiten, die uns die verkettete Liste bereitet hatte, überwunden hatten, begannen wir den Dijkstra-Algorithmus zu implementieren. Wir orientieren uns dabei an der Form des Algorithmus, die im Skript unter Gliederungspunkt 1.4 abgedruckt ist, da dieser Pseudocode schon beinahe richtigem Java-Code entspricht, wodurch unsere Arbeit erleichtert wurde.

Zeilenweise arbeiteten wir den Dijkstra-Algorithmus ab: Wir schauten, welche Methoden in einer jeden Zeile benötigt wurden, und setzten diese Methoden in den Klassen Liste und Knoten um. Beim Programmieren teilten wir uns die Arbeit nicht in dem Sinne auf, dass jeder bestimmte Programmteile implementierte, sondern schrieben alle Methoden gemeinsam.

Dabei versuchten wir den unseren Algorithmus von Beginn an offen für andere Datenstrukturen zu gestalten. So griffen wir in der Klasse Dijkstra zum Beispiel nie direkt auf die Adjazenzmatrix zu, sondern stets nur auf die Methode c(i,j), die das Kantengewicht zwischen den Knoten i und j zurückgibt. Hätte man später statt einer Adjazenzmatrix eine andere Datenstruktur verwenden wollen, so hätte man einzig die Methode c(i,j) ändern müssen.

1.2. Struktur des Programms

Um unser Programm übersichtlicher zu gestalten, unterteilten wir es in mehrere Klassen²:

1.2.1. Die Klasse Ausgabe

Die Klasse Ausgabe hat den Zweck, die kürzeste Entfernung zwischen dem Start- und dem Zielknoten, die zuvor im Dijkstra-Algorithmus berechnet wurde, in eine Textdatei zu schreiben. Dazu wird die zur Klasse gehörige Methode ausgeben() mit einem String -Parameter aufgerufen. Dieser String -Parameter enthält die Länge des kürzesten Weges und wird von einem FileWriter in eine Datei output.txt geschrieben.

1.2.2. 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.

1.2.3. Die Klasse Graph

In der Klasse Graph werden zunächst die Knotenzahl, die Kantenzahl, die Startknoten- und die Zielknotennummer aus der Datei „input.txt“ eingelesen und in int -Variablen gespeichert. Anschließend werden die Gewichte der Kanten eingelesen und in einem zweidimensionalen int -Array, in dessen Feldern zuvor überall der Wert -1 stand, gespeichert. Bei all diesen Operationen müssen zahlreiche Exceptions beachtet werden, die auftreten könnten. Mehr dazu unter im Kapitel „Exception Handling“ (2.4).

Außerdem besitzt die Klasse Graph eine Methode c(i,j), die das Gewicht der Kante (i, j) aus der Adjazenzmatrix abruft und zurückgibt, sowie eine Methode KanteExistiert(i,j), die prüft, ob das Gewicht der Kante (i, j) ungleich -1 ist.

1.2.4. Die Klasse Kno l en

Mithilfe des Konstruktors Knoten() können neue Knoten erzeugt werden. Jeder Knoten ist durch eine Integer-Variable knotennummer definiert, die vom Konstruktor gesetzt wird. Außerdem besitzt in der Front jeder Knoten – außer dem Startknoten – einen Vorgängerknoten. Zuletzt weist jeder Knoten noch einen Wert dist auf, in dem die aktuelle Entfernung des Knotens zum Startknoten gespeichert ist.³

1.2.5. Die Klasse Lis l e

Die Klasse Liste besitzt die Methoden add(), remove(), empty(), min() und type() zum Hinzufügen bzw. Löschen eines Knotens, zum Testen, ob die Front leer ist, zur Bestimmung des Minimums und zum Abrufen des Datenstruktur-Typs.

Abgesehen von min() sind diese Methoden recht simpel aufgebaut: Die Methoden add(), remove() und empty() arbeiten mit einer ArrayList und machen sich die vorgefertigten Funktionen add(), remove() und isEmpty() der ArrayList zu Nutze. Die Methode type() gibt die String -Variable „Liste“ zurück.

Die Bestimmung des Minimums erfolgt in zwei Schritten: Zunächst wird die Distanz des ersten Listenelementes zwischengespeichert. Dabei müssen – um Exceptions zu vermeiden – die Fälle abgefangen werden, in denen die Liste vollständig leer ist und in denen das erste Listenelement nicht gleich im ersten Feld der Liste zu finden ist.

Anschließend wird die Liste vollständig durchlaufen. Bei jedem enthaltenen Knoten wird getestet, ob seine Distanz geringer ist als die zwischengespeicherte Distanz. In diesem Fall wird die zwischengespeicherte Distanz mit der Distanz des aktuellen Knotens überschrieben. So erhält man abschließend das Minimum.

1.3. Fehler und Beobachtungen

Probleme bei der Bestimmung des Minimums

Große Probleme bereitete uns die Bestimmung des Minimums, als wir in der Klasse Liste noch mit head -, naechster - und tail -Zeigern arbeiteten⁴. Die Methode min() war durch zahlreiche Aufrufe wie z.B.

laufzeiger.naechster.naechster.dist

recht unübersichtlich geworden. Zur unserer Verwunderung funktionierte min() bei manchen Input-Dateien einwandfrei, während bei anderen Input-Dateien im letzten Durchlauf des Dijkstra-Algorithmus das Minimum nicht korrekt bestimmt wurde. Nach langem Rätseln erkannten wir, dass die korrekte Bestimmung des Minimums scheinbar davon abhing, wie viele Knoten im vorletzten Durchlauf des Dijkstra-Algorithmus noch in der Front enthalten waren. Den Fehler in min() konnten wir jedoch noch immer nicht finden, woraufhin wir die Klasse Liste mit einer ArrayList statt mit Zeigern implementierten.

Probleme bei großen Input-Dateien

Wir hatten unser Programm bis zu diesem Zeitpunkt stets nur mit Input-Dateien getestet, die wenige Kanten enthielten. Vor ein unerwartetes Problem stellten uns die Input-Dateien „input.txt.200“ und „input.txt.1000“⁵: In unserer ersten Version der Klasse Graph wurde beim Einlesen zunächst ein String -Array mit m Feldern erzeugt; jede Kante wurde in einem eigenen Feld gespeichert, bevor wir dieses Array weiterverwendeten. Die Dateien „input.txt.200“ und „input.txt.1000“ enthielten jedoch rund 20.000 bzw. beinahe 100.000 Kanten. Beim Versuch, ein String -Array dieser Größe zu erzeugen, erhielten wir eine OutOfMemory -Fehlermeldung. Wir konnten die eingelesenen Daten daher nicht zuerst in einem Array zwischenspeichern, sondern mussten sie noch im selben Schleifendurchlauf weiterverarbeiten.

Die if-Abfrage im Dijkstra-Algorithmus

Ungewöhnlich große Probleme bereitete uns anfänglich auch die if -Abfrage innerhalb des Dijkstra-Algorithmus. Wir hatten in der if -Schleife vergessen, einige Bedingungen abzufragen – im Grunde genommen ein leicht zu behebender Fehler, über dem wir jedoch tagelang grübelten. Nachdem wir alle möglichen Fälle, die in der if -Abfrage auftreten konnten, an Beispielen getestet hatten – die Java-Datei enthielt zu diesem Zeitpunkt mehr Kommentare als Code⁶ – fanden wir schließlich unseren Fehler.

1.4. Testdaten

Wir testeten unser Programm zunächst mit einer eigenen Input-Datei⁷, bevor wir die bereitgestellten Dateien verwendeten. Als wir uns später dem Exception Handling widmeten, kam unsere eigene Input-Datei erneut zum Einsatz: Wir wandelten die Datei auf verschiedene Weisen leicht ab⁸, um durch falsche Input-Werte absichtlich Fehlermeldungen zu erzeugen und diese beim Einlesen abzufangen.

2. Herangehensweise Aufgabe 2

2.1. Anpassung des ersten Programms / neue Struktur

Im Zuge von Aufgabe 2 schrieben wir zwei neue Klassen und ein Interface; einige bestehende Klassen mussten wir abändern:

[...]

¹ siehe „Verwaltung der Liste mit einem head -, naechster - und tail -Zeiger“ (4.4)

² siehe auch die Grafik „Beziehungen zwischen den Klassen“ (4.1)

³ Die derzeitige Entfernung eines Knotens zum Startknoten sei im Folgenden als „Distanz“ dieses Knotens bezeichnet.

⁴ siehe „Verwaltung der Liste mit einem head -, naechster - und tail -Zeiger“ (4.4)

⁵ siehe Kapitel „Bereitgestellte Input-Dateien“ (4.3.1)

⁶ siehe den Code-Abschnitt „Probleme bei der if -Abfrage“ (4.4)

⁷ siehe Kapitel „ Eigene Input-Dateien“: input.txt (4.3.2)

⁸ siehe Kapitel „ Eigene Input-Dateien“ (4.3.2)