Diskrete Mathematik II

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

Diskrete Mathematik IIVorlesung 3

27.04.00

• der Algorithmus von Floyd

Foliendesign: cand. geod. Jörg Steinrücken

Lutz Plümer - Diskrete Mathematik II - SS 2000 - Vorlesung 3 - 27.04.00Lutz Plümer - Diskrete Mathematik II - SS 2000 - Vorlesung 3 - 27.04.00

22

Ü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)


33

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


44

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


55

Algorithmus von Floyd: Idee

20

Do

Ha

W15 Für jeden Knoten

35Für jedes Paar Vorgänger / Nachfolger


66

20

Do

Ha

W

Du

K

D15

80

80

20 30

15

150

betrachteterKnoten

Vorgänger

Nachfolger

Algorithmus von Floyd (Beispiel)


77

Do

Ha

W

Du

K

D

20

15

80

80

2030

15

150



88

Do

Ha

W

Du

K

D

20

15

80

80

2030

15

150

Knoten besitztnur Nachfolger


fangen wir wieder an mit Dortmund


99

Do

Ha

W

Du

K

D

30

150

20

15

80

80

20

15

Do

W

35


als nächstes Hagen


1010

8080

Do

Ha

W

Du

K

D

30

150

20

15

80

20

15

35

Do

HaDu

K

D


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


1111

65

Do

Ha

W

Du

K

D

30

150

20

15

80

20

15

35185

115

45



1212

115

Do

Ha

W

Du

K

D

30

150

20

15

80

65

20

15

35185

45

95

165



1313

115

Do

Ha

W

Du

K

D

30

150

20

15

80

65

20

15

35185

45

95

165

Do

Ha

WD



1414

115

Do

Ha

W

Du

K

D

30

150

20

15

80

65

20

15

35185

45

95

165



1515

165

85

165

115

Do

Ha

W

Du

K

D

30

150

20

15

80

65

20

15

35

45

95



1616

65

150

115

Do

Ha

W

Du

K

D

30

20

15

80

65

20

15

35 85

45

95


150


1717

50

115

Do

Ha

W

Du

K

D

30

20

15

80

65

20

15

35 85

45

95

65



1818

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



1919

115

Do

Ha

W

Du

K

D

30

50

20

15

80

65

20

15

35 85

45

95

65



2020

10095

Do

Ha

W

Du

K

D

30

50

20

15

80

65

20

15

35 85

45

65


95


2121

80

80100

Do

Ha

W

Du

K

D

30

50

20

15

65

20

15

35 85

45

65


80


2222

65100

Do

Ha

W

Du

K

D

30

50

20

15

65

20

15

35 85

45

80

65

35



2323

100

Do

Ha

W

Du

K

D

30

50

20

15

65

65

20

15

35 85

45

80

65

35



2424

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!


2525

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; }}}}}


2626

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)


2727

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);

}}

Schönen Dank für Ihre Aufmerksamkeit und

Auf Wiedersehen

Documents

Diskrete Mathematik II