Der Algorithmus von Dijkstra

(Berechnung kürzester Wege in bewerteten Graphen)

GIS Praxis II, Jan Hinzmann, Matr.-Nr.: 2068095

Inhaltsverzeichnis

Edsger Wybe Dijkstra

Graphen

Kürzester Weg?

Algorithmus

Beispiel

Applet

Edsger Wybe Dijkstra

Holländer (1930 Rotterdam– 2002)

erster Programmierer der Niederlande

1972 Turing Preis

"In der Informatik geht es genau so wenig um Computer wie in der Astronomie um Teleskope."

Dijkstra-Algorithmus

findet kürzeste Wege in Graphen

Graphen

Ein Graph G(N,E) hat

N (Node): Menge der Knoten

E (Edge): Menge der Kanten, die Knoten verbinden

Knoten N := {n1, n2, ..., nn}

Kanten E := {e1(ni, nj), ..., e2(nk, nl)}

es gibt gerichtete, gewichtete, benannte, ... Graphen

Graphen (2)

Ein gerichteter Graph

gerichtete Kanten

Ein gewichteter Graph

gewichtete Kanten

Ein benannter Graph

benannte Knoten

kurze Wege in Graphen?

1

1

4

2

4

1

3

5

1

4

2

Kürzester Weg?

Oft gibt es mehrere Wege:

Was ist der kürzeste Weg vom Startknoten s zum Ziel z ?

Weg 1 kostet 9

Weg 2 kostet 6

Weg 3 aber nur 5 !

Die Lösung berechnet der Algorithmus von Dijkstra ...

s

1

1

4

2

4

1

z

1

1

4

2

4

1

z

s

1

1

4

2

4

1

z

s

Algorithmus

Knotenmenge s,k; //s = Startknoten
Knotenmenge opti = {s};
Knotenmenge rest = k\{s};

for ( k aus rest ) do
D[k] = d[s,k] (es gibt Weg);
= ∞ sonst;
done;

while ( rest nicht leer ) do;
wähle k aus rest mit min(D[k]);
opti += {k};
rest = rest -{k};
for ( alle Knoten n von k ) do
D[n] = min(D[n], D[k] + d[k,n]);
done;
done;

In Worten:

Der Startknoten kommt in opti

Alle anderen Knoten in rest

berechne alle Distanzen für die Knoten in rest

verschiebe den Knoten mit der kleinsten Distanz von rest nach opti

berechne die Distanzen für die Knoten in rest neu

wiederhole Schritt 4 und 5 solange, bis rest leer ist

Initialisierung

Iteration

Beispiel

Der Dijkstra-Algorithmus findet die kürzesten Distanzen zu allen anderen Knoten, wenn keine negativen Distanzen (Betrag) zugelassen sind

Für die Navigation kann er abgebrochen werden, sobald der Zielknoten zu Opt hinzugefügt worden ist

3

1

1

4

2

4

1

5

1

4

2

Applet

Dijkstra Applet

http://carbon.cudenver.edu/~hgreenbe/sessions/dijkstra/DijkstraApplet.html

Diskussion

Edsger Wybe Dijkstra

Graphen (gerichtet, gewichtet)

Kürzester Weg?

Algorithmus

Beispiel

Applet

– Danke –

2005-12-02T08:21:43