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)
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
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
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
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
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
5 5
Algorithmus von Floyd: Idee
20
Do
Ha
W15 Für jeden Knoten
35Für jedes Paar Vorgänger / Nachfolger
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
6 6
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
7 7
Do
Ha
W
Du
K
D
20
15
80
80
2030
15
150
Algorithmus von Floyd (Beispiel)
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
8 8
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
9 9
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
10 10
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änger und 3 Nachfolger - wie viele Paare also?
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
11 11
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
12 12
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
13 13
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
14 14
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
15 15
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
16 16
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
17 17
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
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
Algorithmus von Floyd (Beispiel)
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
19 19
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
20 20
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
21 21
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
22 22
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
23 23
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 - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
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!
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
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; }}}}}
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
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)
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 3
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);
}}