Dijkstra - Algorithmus: Unterschied zwischen den Versionen
Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springen| (3 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
| − | |||
| − | |||
Der [[Algorithmus]] ''Shortest Path First'' wurde von Edsger Wybe Dijkstra entwickelt und wird unteranderem in der [[Netzwerktechnik]] verwendet, um den kürzesten Pfad zwischen zwei Knoten in einem Netzwerk zu ermitteln. | Der [[Algorithmus]] ''Shortest Path First'' wurde von Edsger Wybe Dijkstra entwickelt und wird unteranderem in der [[Netzwerktechnik]] verwendet, um den kürzesten Pfad zwischen zwei Knoten in einem Netzwerk zu ermitteln. | ||
| Zeile 16: | Zeile 14: | ||
Der Aufwand des Algorithmus ist O(N^2) | Der Aufwand des Algorithmus ist O(N^2) | ||
| + | |||
| + | ===Psydocode=== | ||
| + | |||
| + | <b>for</b> all v <math> \in </math> V <b>do</b> | ||
| + | <b>g(</b> v <b>)</b> := | ||
| + | <b>parent(</b> v <b>)</b> := <b>nil</b> | ||
| + | <b>done(</b> v <b>)</b> := <b>false</b> | ||
| + | <b>g(</b> s <b>)</b> := 0 | ||
| + | <b>INIT(</b> P <b>)</b> | ||
| + | <b>Update(</b> P , s , 0 <b>)</b> | ||
| + | <b>while</b> v := <b>RemoveMin(</b>P<b>)</b> != <b>nil do</b> | ||
| + | <b>done(</b> v <b>)</b> := true | ||
| + | <b>for</b> all u = N+(v) <b>do</b> | ||
| + | <b>if done(</b> u <b>)</b> = <b>false</b> <math> \wedge </math> <b>g(</b> v <b>)</b> + l(v,u) < <b>g(</b> u <b>)</b> <b>then</b> | ||
| + | <b>g(</b> u <b>)</b> := <b>g(</b> v <b>)</b> + l(u,v) | ||
| + | <b>parent(</b> u <b>)</b> := v | ||
| + | <b>Update(</b> P , u , <b>g(</b> u <b>) )</b> | ||
| + | |||
[[Kategorie:Graphentheorie]] | [[Kategorie:Graphentheorie]] | ||
[[Kategorie:Suchalgorithmus]] | [[Kategorie:Suchalgorithmus]] | ||
Aktuelle Version vom 24. September 2008, 05:31 Uhr
Der Algorithmus Shortest Path First wurde von Edsger Wybe Dijkstra entwickelt und wird unteranderem in der Netzwerktechnik verwendet, um den kürzesten Pfad zwischen zwei Knoten in einem Netzwerk zu ermitteln.
In dem Algorithmus werden alle Knoten in zwei Kategorien unterteilt:
- Gruppe der beurteilten Knoten (E)
- Gruppe der restlichen Knoten (R)
- Geordnete Liste der Pfade (O) anhand ihrer Metrik (steigend)
Für die beurteilten Knoten ist der kürzeste Pfad bekannt.
- Initialsierung der einzelnen Gruppen, E enthält nur den Quellknoten S und R alle anderen Knoten. Die Liste O wird nur mit dem Ein-Segment-Pfad initialisiert, welcher bei S beginnt. Die Kosten der Pfade entspricht der Metrik der Verbindung
- Wenn die Liste O leer ist , oder der erste Pfad die Metrik unendlich hat werden alle übringen Knoten in R als nicht erreichbar markiert und der Algorithmus ist beendet.
- Entnehme den kürzesten Pfad P aus O (1.Element), Entnehme den längsten Pfad V aus O (das letzte Element), wenn V schon in E enthalten ist mache mit Schritt 4 weiter. Sonst ist P der kürzeste Pfad zu V, daher verschiebe V von R nach E und mache bei Schritt 5 weiter.
- Nimm den Knoten W, der vor V in P ist. Wenn die Strecke von S nach W kürzer als die Strecke von S nach V ist, ist P ein Alternativpfad zum Knoten V. Fahre bei Schritt 2 fort.
- Erzeugen einer neuen Gruppe von Pfaden, die mit V beginnen und alle anderen Verbindungen verketten. Die Kosten sind die Summe der Kosten von P und der Verbindung die angehängt wurde. Einfügen der neuen Verbindung zu O und fortfahren mit Schritt 2.
Der Aufwand des Algorithmus ist O(N^2)
Psydocode
for all v <math> \in </math> V do
g( v ) :=
parent( v ) := nil
done( v ) := false
g( s ) := 0
INIT( P )
Update( P , s , 0 )
while v := RemoveMin(P) != nil do
done( v ) := true
for all u = N+(v) do
if done( u ) = false <math> \wedge </math> g( v ) + l(v,u) < g( u ) then
g( u ) := g( v ) + l(u,v)
parent( u ) := v
Update( P , u , g( u ) )
