RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -42
Kürzeste Wege
• Problemstellung:
Suche kürzesten Weg
1. von einem Knoten zu einem anderem
2. von einem Knoten zu allen andere :Single Source Best Path
3. von allen Knoten zu allen anderen: All Pairs Best Path
• Dijkstra-Algorithmus:
• Geg.:
Single Source Best Path
Gerichteter Graph G mit Kostenfunktionen c:
ì= 0
falls w = v
c[v, w] í³
falls Kante von v nach w existiert
î= ¥
falls es keine Kanten v -> w gibt
• Ges.:
Pfad von v0 zu jedem Knoten w mit minimalen Gesamtkosten
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -43
Ablauf Dijkstra-Algorithmus
• Erweitere sukzessive bekannte beste Pfade:
- Kosten können durch Erweiterung von Pfaden nur wachsen
- falls beste Pfade von v0 zu allen anderen Knoten ungleich w höhere Kosten haben als für einen bereits
bekannten Pfad von v nach w, so ist dieser der beste
- bester Pfad hat kleine Zyklen
- bester Pfad hat max. |V| - 1 Kanten
• Notation:
* Sk Menge von k Knoten v mit k besten Pfaden v0 nach v
* D(Sk, v): Kosten des besten Pfades von Knoten in Sk nach v
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -44
Grundidee Dijkstra-Algorithmus
D(Sk, v)
• Obere Schranke D[v] verbesserungsfähig:
- betrachte mögliche Zwischenknoten w
- falls eine Kante von w nach v existiert, so dass gilt
dann:
]
D[w
w
D[w] + c[w, v] < D[v]
D[v] = D[w] + c[w, v]
c[w
, v]
v
v0
D[v]
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -45
Implementierung Dijkstra-Algorithmus
Dijkstra(G,s ){
S = {1}
// 1 sei Ausgangsknoten v0
for(i = 2; i = 2; i <= n; i++){
D[i] = c[1, i];
}
while V\ S ¹ Æ ){
choose w Î V\S with D[w] minimal
S = S È {w}
for esch v in V\S {
D[v] = min(D[v], D[w] + c[w, v]);
}
}
}
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -46
Dijkstra-Algorithmus graphisch
9
Einträge : D[i]
13
14
8
w3
¥
1
10
w4
10
v0:
3
2
9
6
4
0
5
¥
5
7
V/S:{B, C, D, E)
S = {A, C, E, B, D}
w1
w2
7
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -47
Analyse Dijkstra-Algorithmus
• Liefert optimale Lösung, nicht nur Näherung
• Falls Zyklen mit negativen Kosten zugelassen, gibt es keinen
eindeutigen Pfad mit minimalen Kosten mehr
• Komplexität: falls G zusammenhängend,
mit Adjazenzmatrix: O(|V|²)
mit Adjazenzliste und Piority Queue (Heap) für V\S:
1. |E| Kanten in Queue einfügen: |E| * O(log |V|)
2. |V| - 1mal Minimum entfernt: O(|V| * log |V|)
Gesamt: O((|E| + |V|) * log |V|)
meist |V| £ |E|, also: O(|E| * log|V|)
RWTH Aachen, Lehrstuhl für Informatik IX
Floyd-Algorithmus
- All Pairs Best Path
• Geg.:
Gerichteter Graph G mit Kartenfunktion (bewertete Kanten)
ì= 0
für w = v
c[v, w] í³
falls Kante von v nach w existiert
î= ¥
falls es keine Kante von v nach w ginbt
• Ges.:
Pfad von jedem Knoten v zu jeden Knoten w mit minimalen Gesamtkosten
Datenstrukturen und Algorithmen –4 -48
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -49
Ansatz: Dynamische Programmierung
Ak - 1 [i,k]
k
Ak - 1
• Rekursionsgleichung:
j
i
Ak-1[i,j]
Betrachte Zwischenknoten k
Ak[i,j] = min{Ak-1[i, j], Ak-1[i,k] + Ak-1[k, j]}
minimale Kosten, um über Knoten am [1, ..., k von i nach j zu gelangen (aktueller Stand nach k-ten Schritt)
[Vereinfachung: statt Ak[i,j] speichern wir nur A[i, j]
Ablauf: Initialisierung: A[i, j] = c[i, j] für alle i, j Î V
d.h. ausgehend von direkten Kanten
dann: betrachte alle Knoten der Reihe nach als mögliche Zwischenknoten k.
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -50
Implementierung Floyd-Algorithmus
Floyd (A,C,P) { /* A min. Kosten, C Adjazenzmatrix, P ein Zwischenknoten auf bestem Pfad */
for (i = 1,i <= n, i++) {
for (j = 1, j <= n, j++) {
A[i,j] = c[i,j];
P[i,j] = 0;
}
}
falls der Weg über k besser als bisher bester
for (k = 1; k <= n; k++) {
Weg ist
for (i = 1; i <=; i++) {
for (j = 1; j <= n; j++) {
if (A[i, j] > A[i, k] + A[k, j]) {
A[i, j] = A[i, k] + A[k, j];
P[i, j] = k;
}
}
}
}
}
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -51
Floyd-Algorithmus graphisch
5
1
2
4
2
0
¥
¥
4
k=1
5
0
¥
6
2
8
0
6
¥
¥
7
0
0
¥
¥
4
k=2
5
0
¥
6
2
8
0
6
¥
¥
7
0
0
¥
¥
4
k=3
5
0
¥
6
2
8
0
6
9
15
7
0
0
19
11
4
k=4
5
0
13
6
2
8
0
6
9
15
7
0
6
8
3
7
4
Aij > Aik + Akj
Initialisierung
A: 1 1
2
2 0
5
3 ¥
0
¥
4 ¥
5 4
6
3
2
8
0
¥
4
¥
¥
7
0
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -52
Komplexität Floyd-Algorithmus
• 3 geschachtelte Schleifen über i,j,k
• Zeitkomplexität O(|V|³)
• Platzkomplexität O(|V|²)
• Bemerkung: Aus demselben Jahr (1962) stammt ein Algorithmus von
Warshall, der statt Kosten nur die Existenz von Verbindungen
betrachtet (transitive Hülle).
Kern des Algorithmus von Warshall:
if not A[i, j] then A[i, j]= A[i, k] and A[k, j];
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -53
Minimaler Spannbaum
•
•
•
•
•
Geg.: Ungerichteter Graph G=(V,E)
Knoten v, w verbunden: es gibt einen Pfad von v nach w
G verbunden: alle Knotenpaare verbunden
G ist freier Baum: G verbunden, keine Zyklen
Spannbaum: freier Baum G’ = (V, E’), E’ Í E
falls G bewertet: Kosten G’ = Summe der Kosten in E’
• Minimaler Spannbaum (MST) zu G ungerichteter, bewerteter Graph:
Spannbaum mit minimalen Kosten
• MST Property:
alle paarweise dijunkten Teilbäume eines MST sind jeweils über eine minimale Kante verbunden
bzgl..Kosten
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -54
Prim-Algorithmus
• V={1,…,n}, T=(U,E‘) zu konstruierender Minimaler Spannbaum
Prim{
E’ = Æ;
U = {v0};
//Knoten, die schon besucht wurden.
While (U ¹ V) {
choose ( u, v) minimal (u Î U, v Î V\U);
U = U È {v}
E’ = E’ È {(u, v)}
//Greedy-Algorithmus
}
• Komplexität O(|V|2), denn zu jedem neu einzufügenden Knoten
müssen die Kanten zu anderen Knoten überprüft werden
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -55
Prim-Algorithmus graphisch
1
minimaler
Spannbaum
1
5
6
1
1
2
4
6
2
4
3
6
5
5
3
3
5
2
3
4
6
2
5
6
E’ = {(1, 3), (3, 6), (4, 6), (2, 3), (2, 5)} Í E
U = {1, 3, 6, 4, 2, 5} = V
Betrachte Kanten: (1, 2), (1, 3), (1, 4), (2, 3), (3, 5), (3, 6), (5, 6), (4, 6), (2, 5)
6
4
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -56
Union-Find-Strukturen
- Datenstrukturen zur Darstellung disjunktiven Mengen (z.B. disjunkte Teilmengen einer Grundmenge)
- Jede Menge A wird durch einen Repräsentanten x Î A identifiziert
- Operationen:
MakeSet()
Union()
FindSet()
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -57
Union-Find-Strukturen (Realisierungsidee)
- Jede Menge A wird durch einen Baum dargestellt
- Die Knoten und Blätter des Baumes enthalten die Elemente von A
- Die Wurzel des Baums enthält den Repräsentanten von A
- Implementierung: Jeder Knoten enthält einen Zeiger “parent” auf seinem Vorgänger
Bsp:
5
4
7
2
5
5
9
8
3
RWTH Aachen, Lehrstuhl für Informatik IX
Union-Find-Strukturen
• MakeSet(x)
- Erzeugt eine neue Menge Sx dessen einziges Element x ist
- Der Repräsentant von MakeSet(x) ist x
- Disjunktheit:
x darf nicht in einer anderen Menge enthalten sein
x
x
Datenstrukturen und Algorithmen –4 -58
RWTH Aachen, Lehrstuhl für Informatik IX
Union-Find-Strukturen
• z = FindSet(x)
Liefert den Repräsentanten der Menge, die x enthält:
z
y
x
Datenstrukturen und Algorithmen –4 -59
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -60
Union-Find-Strukturen
•
z = Union(x,y)
- Erzeugt die Vereinigung Sx È Sy der Mengen Sx und Sy, wobei x und y nicht die Repräsentanten sein
müssen
- z ist der Repräsentant der Vereinigung Sx È Sy
- Disjunktheit:
Sx und Sy müssen vorher disjunkt sein
-> Sx und Sy werden bei der Vereinigung zerstört
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -61
Union-Find-Strukturen
Ziel/Verwendung: Berechnung von Zusammenhangskomponenten in Graphen;
Berechnung der transitiven Hülle von Relationen
Laufzeitverbesserungen sind möglich durch:
1) Höhenbalancierung
- hänge bei Union den niedrigeren Baum an die Wurzel des höheren Baumes an.
- speichere in jedem Element x die Höhe des darunterhängenden Baumes ab
2) Pfadkompression
- hänge nach jeder Find-Operationen Find(x) die Elemente auf den Pfad von x zur Wurzel an
die Wurzel an.
Ziel jeweils: Pfadlängen möglichst kurz halten, da Find(x) = O(height(x))
RWTH Aachen, Lehrstuhl für Informatik IX
Datenstrukturen und Algorithmen –4 -62
Union-Find-Strukturen
Aufwand (ohne Beweis)
Sei n die Zahl der MakeSet-Operationen (d.h. Anzahl Elemente) und m die Gesamtzahl aller MakeSet,
Union und FindSet-Aufrufe
Dann: Gesamtaufwand bei Verwendung von Höhenbalancierung und Pfadkompression:
O(m * a(n))
mit a £ 5 in allen praktischen Fällen (vgl. Cornen etal)
© Copyright 2024 ExpyDoc
