3URJUDPPLHUSUDNWLNXP

8QLYHUVLWlW ]X .|OQ

6RPPHUVHPHVWHU

² $XVDUEHLWXQJ ²

YRUJHOHJW YRQ

$OH[DQGHU (VVHU

---

Ausarbeitung zum Programmierpraktikum

Alexander Esser

Inhaltsverzeichnis

Herangehensweise Aufgabe 1

3

Vom Blatt auf den Bildschirm

3

Struktur des Programms

4

Die Klasse

Ausgabe

4

Die Klasse

Dijkstra

4

Die Klasse

Graph

4

Die Klasse

Knoten

5

Die Klasse

Liste

5

Fehler und Beobachtungen

5

Testdaten 6

Herangehensweise Aufgabe 2

6

Anpassung des ersten Programms / neue Struktur

6

Änderungen an der Klasse

Ausgabe

7

Die Klasse

Buckets

7

Änderungen an der Klasse

Dijkstra

7

Das Interface

Front

7

Änderungen an der Klasse

Graph

8

Die Klasse

Main

8

Laufzeiten 8

Fehler und Beobachtungen

9

Exception Handling

10

Fazit 11

Anhang 12

Beziehungen zwischen den Klassen

12

Laufzeit 12

Input-Dateien 13

Bereitgestellte Input-Dateien

13

Eigene Input-Dateien

15

Abschnitte aus dem Quellcode

17

­ 2 ­

---

Ausarbeitung zum Programmierpraktikum

Alexander Esser

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 wurde1. 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)

­ 3 ­

---

Ausarbeitung zum Programmierpraktikum

Alexander Esser

1.2.

Struktur des Programms

Um unser Programm übersichtlicher zu gestalten, unterteilten wir es in

mehrere Klassen2:

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

2 siehe auch die Grafik ,,Beziehungen zwischen den Klassen" (4.1)

­ 4 ­

---