Date post: | 02-Jan-2016 |
Category: |
Documents |
Upload: | dane-hodges |
View: | 36 times |
Download: | 4 times |
Institut für Kartographie und GeoinformationProf. Dr. Lutz Plümer
Diskrete Mathematik IIVorlesung 3
27.04.00
• der 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
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)
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
2424