Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Diskrete Mathematik II Vorlesung 3 SS 2001 Algorithmus von Floyd

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

Diskrete Mathematik IIVorlesung 3

SS 2001

Algorithmus von Floyd

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

2 2

Übersicht

• letzte Stunden:– Algorithmus von Dijkstra– alle kürzesten Wege von einem Knoten (1:n)– Datenstrukuren für den Algorithmus von Dijkstra

• Datenstruktur für Graphen mit Kosten– Adjazenzliste

– Adjazenzmatrix

• Datenstruktur für grüne Knoten

• Heute:– Algorithmus von Floyd– kürzeste Wege zwischen allen Paaren von Knoten (n:n)


3 3

Algorithmus von Floyd

• Problem: Bestimmung der kürzesten Wege zwischen allen Paaren von Knoten

• Lösung– iterative Anwendung des Algorithmus von Dijkstra

– besser: Algorithmus von Floyd


4 4

Algorithmus von Floyd: Idee

20

Do

Ha

W15 betrachteter

Knoten

Vorgänger

Nachfolger

35füge neue direkte Kante ein, wenn noch keine Kante vorhanden oder die neue Kante kürzer ist als eine vorhandene


5 5

Algorithmus von Floyd: Idee

20

Do

Ha

W15 Für jeden Knoten

35Für jedes Paar Vorgänger / Nachfolger


6 6

20

Do

Ha

W

Du

K

D15

80

80

20 30

15

150

betrachteterKnoten

Vorgänger

Nachfolger

Algorithmus von Floyd (Beispiel)


7 7

Do

Ha

W

Du

K

D

20

15

80

80

2030

15

150



8 8

Do

Ha

W

Du

K

D

20

15

80

80

2030

15

150

Knoten besitztnur Nachfolger


fangen wir wieder an mit Dortmund


9 9

Do

Ha

W

Du

K

D

30

150

20

15

80

80

20

15

Do

W

35


als nächstes Hagen


10 10

8080

Do

Ha

W

Du

K

D

30

150

20

15

80

20

15

35

Do

HaDu

K

D


Jetzt haben wir 2 Vorgänger und 3 Nachfolger - wie viele Paare also?


11 11

65

Do

Ha

W

Du

K

D

30

150

20

15

80

20

15

35185

115

45



12 12

115

Do

Ha

W

Du

K

D

30

150

20

15

80

65

20

15

35185

45

95

165



13 13

115

Do

Ha

W

Du

K

D

30

150

20

15

80

65

20

15

35185

45

95

165

Do

Ha

WD



14 14

115

Do

Ha

W

Du

K

D

30

150

20

15

80

65

20

15

35185

45

95

165



15 15

165

85

165

115

Do

Ha

W

Du

K

D

30

150

20

15

80

65

20

15

35

45

95



16 16

65

150

115

Do

Ha

W

Du

K

D

30

20

15

80

65

20

15

35 85

45

95


150


17 17

50

115

Do

Ha

W

Du

K

D

30

20

15

80

65

20

15

35 85

45

95

65



18 18

115

Do

Ha

W

Du

K

D

30

50

20

15

80

65

20

15

35 85

45

95

65

Do

Ha

W

Du

K



19 19

115

Do

Ha

W

Du

K

D

30

50

20

15

80

65

20

15

35 85

45

95

65



20 20

10095

Do

Ha

W

Du

K

D

30

50

20

15

80

65

20

15

35 85

45

65


95


21 21

80

80100

Do

Ha

W

Du

K

D

30

50

20

15

65

20

15

35 85

45

65


80


22 22

65100

Do

Ha

W

Du

K

D

30

50

20

15

65

20

15

35 85

45

80

65

35



23 23

100

Do

Ha

W

Du

K

D

30

50

20

15

65

65

20

15

35 85

45

80

65

35



24 24

Implementierung mit der Kostenmatrix-Darstellung

private floyd (float A [n,n], float C [n,n]){ int i, j, k;

for(j = 1; j <= n; j++){for(k = 1; k <=n; k++) //A: Wege

{ A[j,k] = C[j,k]; } //C: Kanten, ggf. }for(i = 1; i <= n; i++){

for(j = 1; j <= n; j++){

for(k = 1; k <= n; k++){

if(A[j,i] + A[i,k] < A[j,k]){ A[j,k] = A[j,i] + A[i,k]; }}}}}

Heute wieder Java!


25 25

Floyd-Erweiterung: Mitführung der kürzesten Wege

private floyd (float A[n,n], float C[n,n], int W[n,n]){ int i, j, k;

for(j = 1; j <= n; j++){for(k = 1; k <=n; k++)

{ A[j,k] = C[j,k]; W[j,k] = }}for(i = 1; i <= n; i++){

for(j = 1; j <= n; j++){

for(k = 1; k <= n; k++){

if(A[j,i] + A[i,k] < A[j,k]){ A[j,k] = A[j,i] + A[i,k]; W[j,k] = i; }}}}}


26 26

Floyd (3)

• Beachten Sie: – Die Ausgabeprozedur setzt voraus, daß ein Weg zwischen 2

Knoten x und y existiert

• Übung:– Wie sehen Sie der Matrix A an, ob ein Weg zwischen 2

Knoten existiert– allgemeiner: Wie sehen Sie der Matrix A an, ob der Graph

zusammenhängend ist– der Graph ist zusammenhängend, wenn zwischen jedem

Paar (a,b) von Knoten ein Weg existiert– beachten Sie, dass wir von gerichteten Graphen sprechen,

also (a,b) (b,a)


27 27

Ausgabe des kürzesten Weges

public weg(int[][] W,int X,int Y) //gibt kürzesten Weg von X nach Y aus

{weg_rekursiv(X,Y);gib Y aus;

}

private weg_rekursiv(int[][] W,int X,int Y) {

if( W[X,Y] = )then gib X aus;else

{ Z = W[X,Y];weg_rekursiv(W,X,Z);weg_rekursiv(W,Z,Y);

}}

Documents

Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Diskrete Mathematik II Vorlesung 3 SS 2001 Algorithmus von Floyd