View
106
Download
0
Category
Preview:
Citation preview
Vortrag von
Stephanie Weirauch
Jens Pleger
Peter Jancke
Frank Wejmelka
WEGE IN GRAPHEN
Inhalt :
1. Graphdefinition und Dijkstra-Algorithmus
2. zweitkürzeste Wege in einem Graphen: Algorithmen von Pollack und Hoffman & Pavley (algorithmusverändernd)
3. zweitkürzeste Wege in einem Graphen. Algorithmus von Azevedo (graphverändernd)
4. Verallgemeinerung auf dritt und k-kürzeste Wege
Vorstellung eines Programms
Graphdefinition
• Graph G=(E,V) besteht aus Knotenmenge V und Kantenmenge E VxV
• Kante (v,w) verbindet Knoten v und w
Beispiel: Straßennetz !
Städte sind Knotenmengen und Straßen bilden Kantenmengen• Jeder Kante (v,w) ist Länge l(v,w)>0 zugeordnet
Der Dijkstra Algorithmus (Greedy - Algorithmus)
• Gegeben Startknoten s und Zielknoten z• Kanten haben Gewichte und sind gerichtet• Für jeden Knoten v suche kürzesten Weg von s nach v• Benutzen von zwei Knotenmengen S und K
(S enthält Knoten, für die der kürzeste Weg von s aus bereits bekannt ist
K (Kandidaten) enthält mögliche Knoten, deren Distanz zu s am geringsten ist)
• Jedem Knoten wird eine Distanz dist(v) zugeordnet• Zu jedem Knoten v wird sein Vorgänger vorg(v) festgehalten
Pseudocode des Dijkstra Algorithmus
(1) S = {}; K = V;
(2) dist(s) = 0; dist(v) = für alle v V \ {s};
(3) vorg(v) = -1 für alle v V; // Es sind noch keine kürzesten Wege bekannt.
(4) while K {} do
(5) wähle Knoten v aus K mit minimaler Distanz dist(v);
(6) S = S {v}; K = K \ {v};
(7) for jeden Nachbarknoten w K von v do
(8) if dist(v) + l(v,w) < dist(w) then
(9) dist(w) = dist(v) + l(v,w); // bisher bekannter kürzester Weg
(10) vorg(w) = v; // von s nach w geht über v
Beispiel für die Anwendung des Dijkstraalgorithmus
3
4
2
1
51
2 6
13
5
3
4
7
4
2
1
5
3
12 6
13
5
3
4
7
32
1
5
41
2 6
13
5
3
4
7
2
1
5
3
41
2
13
5
3
4
76
a (1,2) = 2 < a (1,4) = 13
b (1,2) + a (2,3) = 6 < b (1,5) + a (5,4) = 10< b (1,5) + a (5,3) = 12< a (1,4) = 13
b (1,2) + a (2,5) = 5 < b (1,2) + a (2,3) = 6< a (1,4) = 13
b (1,5) + a (5,4) = 10 < b (1,3) + a (3,4) = 12< a (1,4) = 13
Kürzester Weg von einem Knoten s zu allen anderen Knoten (single source shortest paths problem)
Zweitkürzeste Wege in einem Graphen
• Gesucht ist der zweitkürzeste Weg von s nach z
• Dijkstra ist dem Problem zweitkürzester Wege nicht gewachsen
• Lösung durch:
Algorithmus von Pollack und Hoffman & Pavle (algorithmusverändernd)
Algorithmus von Azevedo (graphverändernd)
• Dynamisches algorithmusveränderndes Verfahren
• Berechne den kürzesten Weg zwischen Start und Zielknoten (m Kanten)
• Entferne jeweils eine Kante des kürzesten Weges und berechne in dem neu entstandenen Graph wieder den kürzesten Weg zwischen Start und Zielknoten (m Berechnungen)
• Der kürzeste Weg dieser m Berechnungen ist der zweitkürzeste Weg zwischen Start und Zielknoten
Algorithmus von Pollack
),..,( 1 meeiw2
Algorithmus von Pollack
Kante 1 oder 2 wird weggelassen - kein kürzester Weg wird berechnet
Kante 3 wird weggelassen - drittkürzester Weg wird berechnet Kante 4 – 8 wird weggelassen - zweitkürzester Weg wird
berechnet
1e 2e 3e 4e 5e 8e7e6e
Der zweitkürzeste Weg von 1 nach 4
32
1
5
41
2 6
13
5
3
4
7
5
3
4
2
11
2 6
13
5
3
4
75
32
411
2 6
13
5
3
4
7
5
3
4
2
11
2 6
13
5
3
4
7 12)(
)43()32()21(
)52(
22
22
2
w
,,,,,w
,e
12)(
)43()32()21(
4,5(
32
32
3
w
,,,,,w
) e
Wegeskürzesten des Länge 1012mit
Wegstezweitkürzeder ist Damit
2
32
222
)δ(w
w w w
13)(
)41(
)21(
12
12
1
w
,w
,e
Der Algorithmus von Pollack findet keine Schleifen
gefunden.werden
Schleifeinnerer mit der Weg
noch eEndschleifoder Start
mit WegstezweitkürzeWeder
Weg.reieschleifenf stezweitkürzeder
nur aber ist Dies ). und (als Weg
sten zweitkürze als Wegorangenen
den berechnet sAlgorithmuDer
42
32 ww
.mit Zyklen auch Wegefindet sAlgorithmuDieser
.nach von Wegkürzester ),,(),...,,(),...,,(
alsoist WegstezweitkürzeDer
, ),( , min :
als sten Wegzweitkürzeden berechne und
mit ),( Kante jede von Knoten jedem von Nimm
berechnet. ebenfallsdamit wirdnach
von ),(),...,,(),,( Wegkürzeste
Der hin.n Zielknotezum Wegekürzesten alle Berechne
gesehen. Wegeskürzesten des Umwegals wird WegstezweitkürzeDer
minmin1min12
1
1
02
1
1
0211
min
zuuvvvvs :w
vuzuduvvsdw
vu
uvwv
z:v
s:vzvvvvs w:
iiiu
n
i
i
ii
n
n
Der Algorithmus von Hoffman & Pavley
z
s
1v
u
minv
1min v
1minv
Der zweitkürzeste Weg von 1 nach 4
32
1
5
41
2 6
13
5
3
4
7
5
3
4
2
11
2 6
13
5
3
4
75
3
4
2
11
2 6
13
5
3
4
7
12)(
)43()32()21(22
22
3
2min
w
,,,,,w
vu
vv
Wegeskürzesten des Länge 1012mit
Wegstezweitkürzeder ist Damit
2
32
12
222
)δ(w
ww w w
5
32
411
2 6
13
5
3
4
7
18)(
)4,3(),35()52()21(
)(
32
32
13
5min
w
,,,,,w
vuvu
vv
13)(
)41(12
12
4
1min
w
,w
vu
vv
Schleifenbeispiel für den Algorithmus von Hoffman & Pavley
1. Die Kanten des kürzeste Wege Baumes zum Zielknoten hin sind violett
2. Die kürzesten Wege von den Endknoten der Kanten 1 und 2 werden betrachtet
3. Algorithmus erschafft zweitkürzesten Weg mit einem Zyklus
1e
2e
Schlingen am Anfang oder Ende
ist. ster Wegzweitkürze ebenfallsder gefunden,
der Wegauch wirdso ist, rt)(undefinie daß
ausgeht,davon man Wenn .5)( ster Weg.zweitkürze
h automatisc wirdundtigt berücksich dungMinimumbilder bei
,
der Weg Damit wird .denn , )(t Eigenschaf
dieerfüllt Kante Die . Betrachte
. und zwischen Wegstezweitkürzeder ist wiederGesucht
321
12
2
321
1
000
, z, z, v, vs, v
vv
w
, z, v, vs, vs
10 vvvu
),v(vvs
zs
nn
i
s
z
1v
2v
3v
Verfahrensvergleich
Pollack Dynamisches Verfahren Berechne den kürzesten Weg w
zwischen s und z Lasse eine Kante e von w weg.
Berechne den kürzesten Weg im Graphen ohne die Kante e
Minimiere über die so entstandenen kürzesten Wege
Kürzester Weg ist gesperrt
Nur schleifenfreie Wege werden gefunden
Hoffman & Pavley Dynamisches Verfahren Berechne den kürzesten Weg w
zwischen s und z Nimm jede Kante e deren
Anfangsknoten ein Knoten von w ist und selbst keine Kante von w ist
Berechne den kürzesten Weg vom Endknoten von e nach z und addiere den Weg nach s.
Minimiere über die so entstandenen kürzesten Wege
Zweitkürzester Weg wird als Variante des kürzesten Weges gesehen
Auch Wege mit Schleifen werden gefunden
Algorithmus von Azevedo modifiziert von Schmid
1e
Azevedo verwendet die Methode Pathdeletion (Wegeverbote).
Statisches Verfahren (verändert nur den Graph nicht aber den kürzeste Wege- Algorithmus)
Vorgehen bei Azevedo
1. Erschaffe einen neuen Startknoten und einen neuen Zielknoten (später).
2. Verdopple den kürzesten Weg ohne erste und letzte Kante bzw Knoten. (Wegeverdopplung)
3. Weise der ersten Kante einen neuen Endknoten zu. (Umleitung)
4. Ziehe alle Kanten über die der kürzeste Weg verlassen werden kann. (Verbindung mit dem Ausgangsgraphen)
Beispiel für den modifizierten Algorithmus von Azevedo
Der kürzeste Weg ist nicht mehr begehbar (X).Der zweit und drittkürzeste Weg sind noch möglich (-- / --).
Der zweitkürzeste Weg (von 1 nach 4)
32
1
5
41
2 6
13
5
3
4
7
5‘
2‘
1
3
7
32
1
5
412
6
13
5
3 7
4
4
5‘
2‘
1
3
7
32
1
5
412
6
13
5
3 7
4
4
Der verdoppelte Weg ist blau.
Die Verbindung mit dem Ausgangsgraphen ist grün.
Die Kanten (2',5) und (5',4) werden nicht gezogen.
Die Kante (1,2) wird zur Kante (1,2').
Problem beim ersten Schritt
Problem:Der Algorithmus von Azevedo kann in dieser Form
einenzweitkürzesten Weg der Form: Schlinge - (alter) kürzester Weg oder (alter) kürzester Weg – Schlinge
nicht erkennen.
Lösung:• Erschaffe einen neuen Startknoten und einen neuen
Zielknoten.• Verbinde den neuen Startknoten mit dem alten
Startknoten durch eine Kante der Länge 0.• Verbinde den alten Zielknoten mit dem neuen
Zielknoten durch eine Kante der Länge 0.
Beispiel für einen erweiterten Graphen incl. ersten Schritt
Der zweitkürzeste Weg (rot) beinhaltet die Schlinge beim Startknoten
Drittkürzeste Wege nach Pollack
.min
Minimum dasdann bilde und Wegkürzesten den berechne
aus Paar ein je Sperre . und zwischen
sten Wegzweitkürzeden und Wegkürzesten den Berechne
:sten Wegesdrittkürze des Berechnung
33
3
212122
12
1111
2
1
i,j
i,j
i,j
jim
m
wδ w
w
)w(w),e(ezs), ... e(ew
), ... e(ew
k kürzeste Wege nach Pollack
.min
Minimum dasdann bilde und Wegkürzesten den berechne
. .. aus Tupel ein je Sperre . und zwischen
..., , Wegekürzesten die Berechne
:Wegeskürzesten 1 des Berechnung
,...,
..,
,...,
11
111
11
1
1
1
1
1
k
k
k
k
k
iik
i,ik
iik
kk
ii
k
m
kkm
wδ w
w
)w(w), ... e(ekzs
), ... e(ew), ... e(ewk
k
Drittkürzeste Wege nach Azevedo
kann.rden rlassen we ve
dieüber Kanten
alle ZieheEndknoten.
neuen einen
bekommt wird, verlassen Wegkürzesteder dieüber Kante Die .verdoppelt
Knoten gen dazugehöri die und Kanten dienur werden Es
den.oppelt wernicht verd muß )( Anfangsweg maximale
gemeinsameDer . sten Wegzweitkürzeden und Wegkürzesten
den Berechne knoten.neuen Zieleinen undn Startknoteneuen einen Erschaffe
2
2 1
2
1
2 2
2122
12
21
11
2 2121
2
2
w
e
), .. ,e(e
e, ... ,ee, eee
), .. ,e (e ww
j
mj
jj
m
k - kürzeste Wege nach Azevedo
kann.werden verlassen
dieüber Kanten alle ZieheEndknoten.neuen einen bekommt wird,
verlassen dieüber Kante Die doppelt.Knoten vergen dazugehöri
die und Kanten dienur werden Es werden.verdoppelt
nicht muß maximal, mit )( Anfangsweg
maximale gemeinsameDer .)mit ( .., , Wegkürzesten -
die Berechne knoten.neuen Zieleinen undn Startknoteneuen einen Erschaffe
:Wegeskürzesten 1 des Berechnung
1
1
2
2211
11
k
lkj
k
m
kj
kj
lj
klkl
i
m
iik
w
we
), .. ,e(e
k, jle, ... ,ee, eee
), .. ,e (ewwwk
k
k
i
Der schlimmste Fall
Graphen. kompletten desn Durchlaufemaligen 1
enden anschliess dem und Wegkürzesten dem aussich ergibt nach von
Wegkürzeste - Der besteht. Zykluseinem ausnur der Graph,ein seiGegeben
k-
zs
k
Recommended