Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Datenstrukturen für den Algorithmus von Dijkstra Diskrete Mathematik II Vorlesung 2

Institut für Kartographie und GeoinformationProf. Dr. Lutz Plümer

Datenstrukturen für den Algorithmus von

Dijkstra

Diskrete Mathematik IIVorlesung 2

SS 2001

Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 2 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 2

2 2

Übersicht

• letzte Stunde– Algorithmus von Dijkstra– alle kürzesten Wege von einem Knoten (1:n)

• heute:– Datenstrukuren für den Algorithmus von Dijkstra

• Datenstruktur für Graphen mit Kosten– Adjazenzliste

– Adjazenzmatrix

• Datenstruktur für grüne Knoten


3 3

algorithm Dijkstra (S){berechne alle kürzesten Wege von S aus}

BLAU = ; GRÜN = {S}; dist(S) = 0;while( GRÜN ) {

wähle K GRÜN, so daß K‘ GRÜN:dist(K) dist(K‘);

färbe K blau;

for( Ki succ(K) ) { if (Ki (GRÜN BLAU) //noch nicht besuchter Knoten

färbe die Kante (K,Ki) rot;

färbe Ki grün;

dist(Ki) = dist(K) + dist(K,Ki); }

... aus der letzten Vorlesung


4 4

Vorgehen

• Repräsentation des Graphen– „ for( Ki succ(K) „– Variante a: Adjazenzmatrix– Variante b: Adjazenzliste

• grüne Knotenmenge


5 5

Adjazenzmatrix

Definition: Knoten, die durch eine Kante verbunden sind, heißen benachbart oder adjazent.

Definition: Die n n Matrix A = (aij) mit

heißt Adjazenzmatrix des Graphen.

sonst

adjazent und falls

false

trueaij

ji KK


6 6

Adjazenzmatrix mit Kosten

sonst K nach K von Kante

der Kosten die k falls

ji

kaij

k

beachte: alle Diagonalelemente sind 0


7 7

0

150

80150030

150

200

20800

Adjazenzmatrix

Do

Ha

W

Du

K

D

20

15

80

80

20 30

15

KDWHaDuDo

K

D

W

Ha

Du

Do

150


8 8

Adjazenzmatrix

• Vorteil: Möglichkeit, in einer Laufzeit von O(1) festzustellen, ob eine Kante von Ki nach Kj existiert.

• Nachteil: hoher Platzbedarf: O(n2)


9 9

Adjazenzliste

• Für jeden Knoten wird eine Liste seiner (Nachfolger-) Nachbarknoten verwaltet.

• Über ein Array der Länge n (n = Anzahl der Knoten) ist jede Liste direkt zugänglich


10 10

Adjazenzliste

Do

Ha

W

D

K

Du

0

150

80150030

150

200

20800

KDWHaDuDo

K

D

W

Ha

Du

DoArray


11 11

Adjazenzliste

Du 80

W 15

Du 30

Ha 20

D 150

K 15

Do

Ha

W

D

K

Du

0

150

80150030

150

200

20800

KDWHaDuDo

K

D

W

Ha

Du

Do

D 20

K 80


12 12

Adjazenzliste

• Vorteil: geringer Platzbedarf: O(n+e) (e = Anzahl der Kanten)

• Nachteil: Um zu prüfen, ob ki und kj benachbart sind, muß die Adjazenzliste von ki durchlaufen und nach kj durchsucht werden.

• aber: für Dijkstra ideal


13 13

Repräsentation der „grünen Knoten“

• die „aktiven“ Knoten• Operationen

– Algorithmus:• füge die Nachfolger des betrachteten Knoten ein• selektiere und entferne das kleinste Element

• Ziel:• Einfügen eines Knotens in O(log n)• Finden und Entfernen des kleinsten Knotens in O(log n)

– Variante A: AVL-Baum– spezialisierter auf diese Anwendung: Heap

Do

Ha

W

Du

K

D

20

80

80

20 30

15

15

W

die „grünen Knoten“

abgearbeitet

noch in Arbeit

noch nicht betrachtet


15 15

Eine neue Datenstruktur: der Heap

• Idee: ein zu jeder Zeit möglichst vollständiger Baum– alle Ebenen bis auf die letzte sind voll besetzt

• Darstellung eines vollständigen Baums in einem Array

• Problem: Bestimmung der Kanten auf Indizes– Index des Vaters– Indizes der beiden Söhne

• Beispiel: Eingabe der sortierten Folge von Zahlen{1 .. 15}

• achten Sie auf die Indizierung


16 16

Einbettung in einen Array:• index(k) = n

– index (k.linkerSohn) = 2 n– index (k.rechterSohn) = 2 n + 1– index (k.vater) =

Eine neue Datenstruktur: Der Heap

2 3

1

14

7

1512

6

1310

5

118

4

9

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

• ein partiell geordneter Baum

• für jeden Teilbaum T‘ mit Wurzel x gilt:

info(y) info(x)für jeden Knoten y von T‘{in der Wurzel steht das Minimum des Teilbaums}

2n


17 17

Entfernen des kleinsten Elements

algorithm deletemin (H)

/*lösche das minimale Element des Heaps und gib es aus*/

gib den Eintrag der Wurzel aus;lösche die Wurzel und ersetze sie durch die letzte Position im Baumsei p die Wurzel mit den Söhnen q und r;

while q oder r existieren und ((info (p) > info (q)) oder (info (p) > info (r)))vertausche p mit dem kleineren der beiden Söhnebenenne p, q, r um

2 3

1

14

7

1512

6

1310

5

118

4

9

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


18 18






2 3

1

14

7

1512

6

1310

5

118

4

9

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


19 19






2 3

14

7

1512

6

1310

5

118

4

9

2 3 4 5 6 7 8 9 10 11 12 13 14 15


20 20






2 3

14

7

15

12

6

1310

5

118

4

9

2 3 4 5 6 7 8 9 10 11 12 13 1415


21 21






15 3

14

7

2

12

6

1310

5

118

4

9

2 3 4 5 6 7 8 9 10 11 12 13 1415


22 22






4 3

14

7

2

12

6

1310

5

118

15

9

2 34 5 6 7 8 9 10 11 12 13 1415


23 23






4 3

14

7

2

12

6

1310

5

1115

8

9

2 34 5 6 78 9 10 11 12 13 1415


24 24

Einfügen eines neuen Elements

algorithm insert (H,e)

/*füge Element e in H ein*/

füge einen neuen Knoten q mit Eintrag e an der ersten freien Position der untersten Ebene des Baumes ein, eröffne ggf. neue Ebene;p sei der Vater von q;

while p existiert und (info (q) < info (p)) do vertausche p und q benenne p und q um

2 3

1

7

12

6

10

5

118

4

9

1 2 3 4 5 6 7 8 9 10 11 12

Beispiel: füge „0“ ein


25 25






2 3

1

7

12

6

10

5

118

4

9

1 2 3 4 5 6 7 8 9 10 11 12


0

0


26 26






2 3

1

7

12

0

10

5

118

4

9

1 2 3 4 5 67 8 9 10 11 12


0

6

1313 / 2 = 6


27 27






2 0

1

7

12

3

10

5

118

4

9

1 2 34 5 67 8 9 10 11 12


0

6


28 28






2 1

0

7

12

3

10

5

118

4

9

12 34 5 67 8 9 10 11 12


0

6


29 29

Für „Kenner“

• Bestimmen des Vaterknotens: ganzzahlige Division durch 2

• Bestimmen des Sohns: Multiplikation mit 2– ggf. Addition von 1

• auf Maschinenebene einfache Bit-Schiftoperationen

Für „Hacker“ ?

Documents

Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Datenstrukturen für den Algorithmus von Dijkstra Diskrete Mathematik II Vorlesung 2