Algorithmus von Dijkstra < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:44 Di 17.01.2006 | | Autor: | Gerd52 |
Hallo Forumsfreunde,
ich habe ein gerichtetes Netzwerk und würde gerne wissen, wie man mit Hilfe des Dijkstra-Algorithmus für das abgebildete gerichtete Netzwerk:
[Dateianhang nicht öffentlich]
einen Wurzelbaum mit Wurzel [mm]A[/mm] an der Ecke links konstruiert.
Dabei interessiert mich die jeweilige Länge des zu den Ecken führenden kürzesten Weges.
bin für jede Hilfe dankebar
grüße
Gerd
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
Hallo Gerd,
![[willkommenir]](/images/smileys/willkommenir.png "[willkommenir]")
So wie Du dein Problem beschreibst, scheint mir ![[]](/images/popup.gif) folgendes Java-Applet genau das Richtige zu sein. Wenn dir ein Schritt unklar sein sollte, so frag' einfach nochmal nach.
Viele Grüße
Karl
|
|
|
| |
|
Hallo Gerd und Karl,
und hallo Freunde kurzer Wege - die werden ja trotz Existenz nicht immer in Anspruch genommen ...,
ich hab mir das Java-Applet von Karl noch nicht angeschaut, moechte trotzdem alternativ vorschlagen, den Dijkstra-Algorithmus an diesem Beispiel selber einmal von Hand und Kopf auszuprobieren, denn dann versteht man ihn vielleicht besser.
Kuerzen wir ihn mal DA ab.
DA konstruiert ja einen Kuerzeste-Wege-Baum mit Wurzel A. In jedem Schritt haelt DA eine Teilmenge S der Knotenmenge, und fuer diese ist der Wert d(A,v) [mm] (v\in [/mm] S) schon gleich der Laenge eines kuerzesten Weges von A nach v im Graphen bzw. Netzwerk.
Fuer alle anderen Knoten [mm] v\in V\setminus [/mm] S ist d(A,v) eine obere Schranke fuer
die Laenge eines kuerzesten Weges von A nach v.
Anfangs ist [mm] S=\emptyset, [/mm] und d(A,A)=0 und [mm] d(A,v)=\infty [/mm] (halt eine genuegend grosse Zahl)
fuer alle [mm] v\neq [/mm] A.
In jedem Schritt nimmt DA dann ein [mm] v\in V\setminus [/mm] S mit minimalem Wert d(A,v) und
testet alle oberen Schranken, ob sie verbessert werden koennen unter Zuhilfenahme von v.
Gleichzeitig wird eine Funktion [mm] \pi [/mm] konstruiert, die am Ende den Wurzelbaum - oder
Kuerzeste-Wege-baum- konstruiert: [mm] \pi(v) [/mm] wird dann der direkte Vorgaenger von v
auf einem kuerzestenPfad zur Wurzel sein. Anfangs ist [mm] \pi(v) [/mm] = A fuer alle v.
Ich wuerd mir mal fuer das Beispiel fuer jeden Schritt die Menge S und die Werte d(A,v)
und [mm] \pi(v) (v\in [/mm] V)
konstruieren, also anfangs
[mm] S=\{A\}, [/mm] d(A,v)= 0 fuer v=A und [mm] \infty [/mm] sonst.
Dann wird DA zunaechst denKnoten A nehmen und die Distanzen zu allen seinen Nachbarn aktualisieren. Dann wir er den Knoten nehmen, der Abstand 3 zu A hat usw.
Eine sehr gute Beschreibung findet Ihr zB in dem Lehrbuch von Norbert Blum ''Algorithmen und Datenstrukturen - Eine anwendungsorientierte Einfuehrung''.
Dieses Buch ist im uebrigen insgesamt sehr gut geschrieben und daher unbedingt
zu empfehlen.
Viele Gruesse,
Mathias
PS. Fuer einige im Forum sollen ja auch die Wege zum Autor des oben genannten Buches - wie so einige andere Wege auch - besonders kurz sein....
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:18 Di 17.01.2006 | | Autor: | Gerd52 |
Hallo Karl und Matthias,
ich muss mich mal wirklich für die schnelle Hilfe bedanken.
Ich komme aber erst heute Abend zur genauen Bearbeitung eurer Vorschläge. Das Prinzip des Algorithmus scheint ja einfach zu sein, aber man muss erst den richtigen Ansatz finden.
Vielen Dank und einen schönen Nachmittag wünsche ich
Gerd
|
|
|
|
