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

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

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 1 . 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 siehe „Verwaltung der Liste mit einem head-, naechster- und tail-Zeiger“ (4.4)

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

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.

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

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

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

Methode KanteExistiert(i,j), die prüft, ob das Gewicht der Kante (i, j) ungleich -1 ist.

1.2.4. Die Klasse Knoten

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

1.2.5. Die Klasse Liste

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

Große Probleme bereitete uns die Bestimmung des Minimums, als wir in der Klasse Liste noch mit head-, naechster- und tail-Zeigern arbeiteten 4 . 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

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

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