Dijkstra - Algorithmus - Versionsgeschichte

EagleEye am 24. September 2008 um 05:31 Uhr

2008-09-24T05:31:35Z

← Nächstältere Version		Version vom 24. September 2008, 05:31 Uhr
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.

84.190.78.101 am 23. September 2008 um 23:16 Uhr

2008-09-23T23:16:31Z

← Nächstältere Version		Version vom 23. September 2008, 23:16 Uhr
Zeile 30:		Zeile 30:
	<b>for</b> all u = N+(v) <b>do</b>		<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>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>~~done~~(</b> u <b>)</b> := <b>~~false~~</b>		<b>g(</b> u <b>)</b> := <b>g(</b> v <b>)</b> + l(u,v)
	<b>parent(</b> u <b>)</b> := v		<b>parent(</b> u <b>)</b> := v
	<b>Update(</b> P , u , <b>g(</b> u <b>) )</b>		<b>Update(</b> P , u , <b>g(</b> u <b>) )</b>

84.190.78.101 am 23. September 2008 um 21:50 Uhr

2008-09-23T21:50:31Z

@@ Zeile 16: / Zeile 16: @@
 Der Aufwand des Algorithmus ist O(N^2)
 [[Kategorie:Graphentheorie]]
 [[Kategorie:Suchalgorithmus]]

EagleEye: hat Shortest Path First - Algorithmus nach Dijkstra - Algorithmus verschoben

2007-07-20T09:20:03Z

hat Shortest Path First - Algorithmus nach Dijkstra - Algorithmus verschoben

← Nächstältere Version		Version vom 20. Juli 2007, 09:20 Uhr
(kein Unterschied)

EagleEye am 20. Juli 2007 um 09:16 Uhr

2007-07-20T09:16:39Z

← Nächstältere Version		Version vom 20. Juli 2007, 09:16 Uhr
Zeile 11:		Zeile 11:
	# 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		# 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.		# 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 2 weiter. ~~sonst~~ ist P der kürzeste Pfad zu V, daher verschiebe V von R nach E.		# 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.		# 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)		Der Aufwand des Algorithmus ist O(N^2)
	~~[[Kategorie:Optimierungsalgorithmus]]~~
	[[Kategorie:Graphentheorie]]		[[Kategorie:Graphentheorie]]
	[[Kategorie:Suchalgorithmus]]		[[Kategorie:Suchalgorithmus]]

EagleEye: Die Seite wurde neu angelegt: {{ Der Algorithmus ''Shortest Path First'' wurde von Edsger Wybe Dijkstra entwickelt und wird unteranderem in der Netzwerktechnik verwendet, um den kürzesten ...

2007-07-19T22:03:00Z

Die Seite wurde neu angelegt: {{ Der Algorithmus ''Shortest Path First'' wurde von Edsger Wybe Dijkstra entwickelt und wird unteranderem in der Netzwerktechnik verwendet, um den kürzesten ...

Neue Seite

{{

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 2 weiter. sonst ist P der kürzeste Pfad zu V, daher verschiebe V von R nach E.
# 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)
[[Kategorie:Optimierungsalgorithmus]]
[[Kategorie:Graphentheorie]]
[[Kategorie:Suchalgorithmus]]