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