View
32
Download
0
Category
Preview:
DESCRIPTION
Diskrete Mathematik II. Vorlesung 3 27.04.00 der Algorithmus von Floyd. Foliendesign: cand. geod. Jörg Steinrücken. Übersicht. letzte Stunden: Algorithmus von Dijkstra alle kürzesten Wege von einem Knoten ( 1:n ) Datenstrukuren für den Algorithmus von Dijkstra - PowerPoint PPT Presentation
Citation preview
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)
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
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
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
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
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
55
Algorithmus von Floyd: Idee
20
Do
Ha
W15 Für jeden Knoten
35Für jedes Paar Vorgänger / Nachfolger
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
66
20
Do
Ha
W
Du
K
D15
80
80
20 30
15
150
betrachteterKnoten
Vorgänger
Nachfolger
Algorithmus von Floyd (Beispiel)
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
77
Do
Ha
W
Du
K
D
20
15
80
80
2030
15
150
Algorithmus von Floyd (Beispiel)
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
88
Do
Ha
W
Du
K
D
20
15
80
80
2030
15
150
Knoten besitztnur Nachfolger
Algorithmus von Floyd (Beispiel)
fangen wir wieder an mit Dortmund
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
99
Do
Ha
W
Du
K
D
30
150
20
15
80
80
20
15
Do
W
35
Algorithmus von Floyd (Beispiel)
als nächstes Hagen
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
1010
8080
Do
Ha
W
Du
K
D
30
150
20
15
80
20
15
35
Do
HaDu
K
D
Algorithmus von Floyd (Beispiel)
Jetzt haben wir 2 Vorgänge und 3 Nachfolger - wie viele Paare also?
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
1111
65
Do
Ha
W
Du
K
D
30
150
20
15
80
20
15
35185
115
45
Algorithmus von Floyd (Beispiel)
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
1212
115
Do
Ha
W
Du
K
D
30
150
20
15
80
65
20
15
35185
45
95
165
Algorithmus von Floyd (Beispiel)
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
1313
115
Do
Ha
W
Du
K
D
30
150
20
15
80
65
20
15
35185
45
95
165
Do
Ha
WD
Algorithmus von Floyd (Beispiel)
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
1414
115
Do
Ha
W
Du
K
D
30
150
20
15
80
65
20
15
35185
45
95
165
Algorithmus von Floyd (Beispiel)
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
1515
165
85
165
115
Do
Ha
W
Du
K
D
30
150
20
15
80
65
20
15
35
45
95
Algorithmus von Floyd (Beispiel)
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
1616
65
150
115
Do
Ha
W
Du
K
D
30
20
15
80
65
20
15
35 85
45
95
Algorithmus von Floyd (Beispiel)
150
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
1717
50
115
Do
Ha
W
Du
K
D
30
20
15
80
65
20
15
35 85
45
95
65
Algorithmus von Floyd (Beispiel)
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
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
Algorithmus von Floyd (Beispiel)
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
1919
115
Do
Ha
W
Du
K
D
30
50
20
15
80
65
20
15
35 85
45
95
65
Algorithmus von Floyd (Beispiel)
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
2020
10095
Do
Ha
W
Du
K
D
30
50
20
15
80
65
20
15
35 85
45
65
Algorithmus von Floyd (Beispiel)
95
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
2121
80
80100
Do
Ha
W
Du
K
D
30
50
20
15
65
20
15
35 85
45
65
Algorithmus von Floyd (Beispiel)
80
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
2222
65100
Do
Ha
W
Du
K
D
30
50
20
15
65
20
15
35 85
45
80
65
35
Algorithmus von Floyd (Beispiel)
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
2323
100
Do
Ha
W
Du
K
D
30
50
20
15
65
65
20
15
35 85
45
80
65
35
Algorithmus von Floyd (Beispiel)
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
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!
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
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; }}}}}
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
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)
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
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
Recommended