TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 319

Aus VoWi
Zur Navigation springen Zur Suche springen

In der folgenden schematisch skizzierten Landkarte sind für eine bestimmte Fracht die Transportkosten zwischen den einzelnen Orten angegeben. Welches ist der billigste Weg vom Ort P_1 zum Ort P_{10}?

Bsp211 1.png

Theorie - Algorithmus von Dijkstra[Bearbeiten]

Siehe Theorie_06.12.2005_Graphentheorie#K.C3.BCrzeste_Wege_.28Dijkstra-Algorithmus.29!

Dijkstra-Kochrezept von Superwayne[Bearbeiten]

Das Ziel des Dijkstra-Algorithmus ist, die kürzeste Distanz von einem Anfangsknoten für einen Endknoten oder alle anderen Knoten zu finden. Am einfachsten ist dafür eine tabellarische Lösung. Für jeden Knoten wird eine Spalte angelegt, sowie eine für den ausgewählten Knoten und den Vorgängerknoten. Mit jeder Zeile "wächst" unser Wissen über den Graph. Eine Zeile ist also eine Iteration, mit der wir mehr wissen über den Graph und seine Zusammensetzung erlangen.

  1. Anfang: Am Anfang wissen wir natürlich noch nichts über den Graph, wir stehen bildlich gesprochen vor dem Anfangsknoten des Graphen und können nur diesen Anfangsknoten sehen. Deshalb legen wir in der Tabelle die erste Zeile an und setzen für den Anfangsknoten die Distanz 0 und für alle anderen Knoten die Distanz unendlich, da wir diese nicht "sehen" können, also noch kein Wissen über diese haben.
  2. Auswählen des nächsten Knotens: Nun müssen wir uns entscheiden, welcher Knoten als nächstes ausgewählt werden soll. Dazu wählen wir den Knoten aus der aktuellen Zeile, der den geringsten Wert (Distanz) aufweist und noch nie ausgewählt wurde. Wir wählen diesen Knoten als Nachfolger aus, d.h. wir vermerken dies in der Spalte Ausgewählter Knoten und setzen den aktuellen Knoten als Vorgänger. Gibt es keinen Knoten mehr zum Auswählen oder ist der ausgewählte Knoten unser gesuchter Knoten, so sind wir fertig.
  3. Bewertung des Knotens: Nachdem wir einen neuen Knoten ausgewählt haben, gehen wir alle noch nicht ausgewählten Knoten Spalte für Spalte durch. Ist der Knoten in der Spalte kein Nachbarknoten, so übernehmen wir die Distanz einfach in die aktuelle Zeile. Ist der Knoten ein Nachbarknoten, so prüfen wir, ob die Distanz über den aktuellen Knoten kleiner ist. Wenn ja, schreiben wir die aktuelle Distanz in die Spalte, wenn nein, übernehmen wir die Distanz aus der vorherigen Zeile. Das machen wir für alle Knoten bzw. alle Spalten. Anschließend gehen wir über zu Auswählen des nächsten Knotens (Punkt 2).

Den kürzesten Weg kann man nun rekonstruieren, in dem man vom letzten ausgewählten Knoten den Vorgänger aus der Tabelle abliest und von diesem Vorgängerknoten wieder den Vorgängerknoten, usw. usf. wodurch man dann den kürzesten Pfad erhält.

Lösungsvorschlag von mnemetz[Bearbeiten]

Basierend auf f.thread:37700

Tabellarische Lösung[Bearbeiten]

Iteration P_{1} P_{2} P_{3} P_{4} P_{5} P_{6} P_{7} P_{8} P_{9} P_{10} Auswahl Vorgänger
0 0 \infty \infty \infty \infty \infty \infty \infty \infty \infty P_{1}
1 3 6 10 1 \infty \infty \infty \infty \infty P_{5} P_{1}
2 3 6 10 \infty \infty \infty 11 \infty P_{2} P_{1}
3 5 11 9 \infty 11 \infty P_{3} P_{2}
4 9 8 \infty \infty P_{7} P_{3}
5 9 11 13 16 P_{4} P_{7}
6 13 10 P_{9} P_{4}
7 12 19 P_{8} P_{9}
8 14 P_{10} P_{8}

Kürzester Weg somit: P_{1} \rightarrow P_{2} \rightarrow P_{3} \rightarrow P_{7} \rightarrow P_{4} \rightarrow P_{9} \rightarrow P_{8} \rightarrow P_{10}

Edit: es gibt noch einen zweiten möglichen kürzesten Weg: P_{1} \rightarrow P_{2} \rightarrow P_{3} \rightarrow P_{4} \rightarrow P_{9} \rightarrow P_{8} \rightarrow P_{10}

tomel: Ich würde eher die zweite Lösung für die korrekte halten, weil im "orangen Buch" auf Seite 69 bei der Beschreibung des Algorithmus in Punkt 2 als Bedingung > und nicht >= angegeben wird. Dh der Vorgänger von P4 bleibt P3, auch wenn er zu denselben Kosten von P7 erreichbar ist, würde ich sagen.

Alternative Lösung[Bearbeiten]

Die Tabelle in der obigen Lösung ist meines Erachtens nicht ganz richtig, da nicht immer der absolut kürzeste, dem System zum Zeitpunkt bekannte, Weg gewählt wird (der auch für die Lösung gesehen sein kann). Ich habe deshalb die Tabelle noch einmal aufgebaut. Das Ergebnis ist zwar das gleiche, aber man kann dann den Algorithmus vielleicht leichter nachvollziehen. Dieses Beispiel ist vor allem deshalb interessant, da es Spezialfälle enthält.

P_1 P_2 P_3 P_4 P_5 P_6 P_7 P_8 P_9 P_{10} Ausgewählter Knoten Vorgängerknoten
0 P_1 -
3 6 10 1 P_5 P_1
3 6 10 11 P_2 P_1
5 10 11 11 P_3 P_2
9 11 8 11 P_7 P_3
9 11 13 11 16 P_4 P_7
11 13 10 16 P_9 P_4
11 12 16 P_6 P_7
12 16 P_8 P_9
14 P_{10} P_8

Rückwärts ausgelesen ist die Lösung demnach P_{10} \leftarrow P_{8} \leftarrow P_{9} \leftarrow P_{4} \leftarrow P_{7} \leftarrow P_{3} \leftarrow P_{2} \leftarrow P_{1} bzw. P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow P_7 \rightarrow P_4 \rightarrow P_9 \rightarrow P_8 \rightarrow P_{10}.

-- Superwayne 20:30, 27. Nov. 2014 (CET)

Anmerkung: Dies ist meiner Meinung nach nicht korrekt. Wenn ich für einen Punkt einen Wert w bekomme und im Laufe des Algorithmus den gleichen Wert w zum selben Punkt ausgehend von einem anderen Vorgänger bekomme, so wird immer nur der erste kürzeste Weg in Betracht gezogen und nicht beide oder der letzte.

graphische Lösung (neu gezeichnet von Bubbleyellow)[Bearbeiten]

219.jpg

Siehe auch:Vorlage:DefinitionVorlage:Extern>

In der folgenden schematisch skizzierten Landkarte sind für eine bestimmte Fracht die Transportkosten zwischen den einzelnen Orten angegeben. Welches ist der billigste Weg vom Ort P_1 zum Ort P_{10}?

Bsp211 1.png

Theorie - Algorithmus von Dijkstra[Bearbeiten]

Siehe Theorie_06.12.2005_Graphentheorie#K.C3.BCrzeste_Wege_.28Dijkstra-Algorithmus.29!

Dijkstra-Kochrezept von Superwayne[Bearbeiten]

Das Ziel des Dijkstra-Algorithmus ist, die kürzeste Distanz von einem Anfangsknoten für einen Endknoten oder alle anderen Knoten zu finden. Am einfachsten ist dafür eine tabellarische Lösung. Für jeden Knoten wird eine Spalte angelegt, sowie eine für den ausgewählten Knoten und den Vorgängerknoten. Mit jeder Zeile "wächst" unser Wissen über den Graph. Eine Zeile ist also eine Iteration, mit der wir mehr wissen über den Graph und seine Zusammensetzung erlangen.

  1. Anfang: Am Anfang wissen wir natürlich noch nichts über den Graph, wir stehen bildlich gesprochen vor dem Anfangsknoten des Graphen und können nur diesen Anfangsknoten sehen. Deshalb legen wir in der Tabelle die erste Zeile an und setzen für den Anfangsknoten die Distanz 0 und für alle anderen Knoten die Distanz unendlich, da wir diese nicht "sehen" können, also noch kein Wissen über diese haben.
  2. Auswählen des nächsten Knotens: Nun müssen wir uns entscheiden, welcher Knoten als nächstes ausgewählt werden soll. Dazu wählen wir den Knoten aus der aktuellen Zeile, der den geringsten Wert (Distanz) aufweist und noch nie ausgewählt wurde. Wir wählen diesen Knoten als Nachfolger aus, d.h. wir vermerken dies in der Spalte Ausgewählter Knoten und setzen den aktuellen Knoten als Vorgänger. Gibt es keinen Knoten mehr zum Auswählen oder ist der ausgewählte Knoten unser gesuchter Knoten, so sind wir fertig.
  3. Bewertung des Knotens: Nachdem wir einen neuen Knoten ausgewählt haben, gehen wir alle noch nicht ausgewählten Knoten Spalte für Spalte durch. Ist der Knoten in der Spalte kein Nachbarknoten, so übernehmen wir die Distanz einfach in die aktuelle Zeile. Ist der Knoten ein Nachbarknoten, so prüfen wir, ob die Distanz über den aktuellen Knoten kleiner ist. Wenn ja, schreiben wir die aktuelle Distanz in die Spalte, wenn nein, übernehmen wir die Distanz aus der vorherigen Zeile. Das machen wir für alle Knoten bzw. alle Spalten. Anschließend gehen wir über zu Auswählen des nächsten Knotens (Punkt 2).

Den kürzesten Weg kann man nun rekonstruieren, in dem man vom letzten ausgewählten Knoten den Vorgänger aus der Tabelle abliest und von diesem Vorgängerknoten wieder den Vorgängerknoten, usw. usf. wodurch man dann den kürzesten Pfad erhält.

Lösungsvorschlag von mnemetz[Bearbeiten]

Basierend auf f.thread:37700

Tabellarische Lösung[Bearbeiten]

Iteration P_{1} P_{2} P_{3} P_{4} P_{5} P_{6} P_{7} P_{8} P_{9} P_{10} Auswahl Vorgänger
0 0 \infty \infty \infty \infty \infty \infty \infty \infty \infty P_{1}
1 3 6 10 1 \infty \infty \infty \infty \infty P_{5} P_{1}
2 3 6 10 \infty \infty \infty 11 \infty P_{2} P_{1}
3 5 11 9 \infty 11 \infty P_{3} P_{2}
4 9 8 \infty \infty P_{7} P_{3}
5 9 11 13 16 P_{4} P_{7}
6 13 10 P_{9} P_{4}
7 12 19 P_{8} P_{9}
8 14 P_{10} P_{8}

Kürzester Weg somit: P_{1} \rightarrow P_{2} \rightarrow P_{3} \rightarrow P_{7} \rightarrow P_{4} \rightarrow P_{9} \rightarrow P_{8} \rightarrow P_{10}

Edit: es gibt noch einen zweiten möglichen kürzesten Weg: P_{1} \rightarrow P_{2} \rightarrow P_{3} \rightarrow P_{4} \rightarrow P_{9} \rightarrow P_{8} \rightarrow P_{10}

tomel: Ich würde eher die zweite Lösung für die korrekte halten, weil im "orangen Buch" auf Seite 69 bei der Beschreibung des Algorithmus in Punkt 2 als Bedingung > und nicht >= angegeben wird. Dh der Vorgänger von P4 bleibt P3, auch wenn er zu denselben Kosten von P7 erreichbar ist, würde ich sagen.

Alternative Lösung[Bearbeiten]

Die Tabelle in der obigen Lösung ist meines Erachtens nicht ganz richtig, da nicht immer der absolut kürzeste, dem System zum Zeitpunkt bekannte, Weg gewählt wird (der auch für die Lösung gesehen sein kann). Ich habe deshalb die Tabelle noch einmal aufgebaut. Das Ergebnis ist zwar das gleiche, aber man kann dann den Algorithmus vielleicht leichter nachvollziehen. Dieses Beispiel ist vor allem deshalb interessant, da es Spezialfälle enthält.

P_1 P_2 P_3 P_4 P_5 P_6 P_7 P_8 P_9 P_{10} Ausgewählter Knoten Vorgängerknoten
0 P_1 -
3 6 10 1 P_5 P_1
3 6 10 11 P_2 P_1
5 10 11 11 P_3 P_2
9 11 8 11 P_7 P_3
9 11 13 11 16 P_4 P_7
11 13 10 16 P_9 P_4
11 12 16 P_6 P_7
12 16 P_8 P_9
14 P_{10} P_8

Rückwärts ausgelesen ist die Lösung demnach P_{10} \leftarrow P_{8} \leftarrow P_{9} \leftarrow P_{4} \leftarrow P_{7} \leftarrow P_{3} \leftarrow P_{2} \leftarrow P_{1} bzw. P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow P_7 \rightarrow P_4 \rightarrow P_9 \rightarrow P_8 \rightarrow P_{10}.

-- Superwayne 20:30, 27. Nov. 2014 (CET)

Anmerkung: Dies ist meiner Meinung nach nicht korrekt. Wenn ich für einen Punkt einen Wert w bekomme und im Laufe des Algorithmus den gleichen Wert w zum selben Punkt ausgehend von einem anderen Vorgänger bekomme, so wird immer nur der erste kürzeste Weg in Betracht gezogen und nicht beide oder der letzte.

graphische Lösung (neu gezeichnet von Bubbleyellow)[Bearbeiten]

219.jpg

Siehe auch:Vorlage:DefinitionVorlage:Extern>

In der folgenden schematisch skizzierten Landkarte sind für eine bestimmte Fracht die Transportkosten zwischen den einzelnen Orten angegeben. Welches ist der billigste Weg vom Ort P_1 zum Ort P_{10}?

Bsp211 1.png

Theorie - Algorithmus von Dijkstra[Bearbeiten]

Siehe Theorie_06.12.2005_Graphentheorie#K.C3.BCrzeste_Wege_.28Dijkstra-Algorithmus.29!

Dijkstra-Kochrezept von Superwayne[Bearbeiten]

Das Ziel des Dijkstra-Algorithmus ist, die kürzeste Distanz von einem Anfangsknoten für einen Endknoten oder alle anderen Knoten zu finden. Am einfachsten ist dafür eine tabellarische Lösung. Für jeden Knoten wird eine Spalte angelegt, sowie eine für den ausgewählten Knoten und den Vorgängerknoten. Mit jeder Zeile "wächst" unser Wissen über den Graph. Eine Zeile ist also eine Iteration, mit der wir mehr wissen über den Graph und seine Zusammensetzung erlangen.

  1. Anfang: Am Anfang wissen wir natürlich noch nichts über den Graph, wir stehen bildlich gesprochen vor dem Anfangsknoten des Graphen und können nur diesen Anfangsknoten sehen. Deshalb legen wir in der Tabelle die erste Zeile an und setzen für den Anfangsknoten die Distanz 0 und für alle anderen Knoten die Distanz unendlich, da wir diese nicht "sehen" können, also noch kein Wissen über diese haben.
  2. Auswählen des nächsten Knotens: Nun müssen wir uns entscheiden, welcher Knoten als nächstes ausgewählt werden soll. Dazu wählen wir den Knoten aus der aktuellen Zeile, der den geringsten Wert (Distanz) aufweist und noch nie ausgewählt wurde. Wir wählen diesen Knoten als Nachfolger aus, d.h. wir vermerken dies in der Spalte Ausgewählter Knoten und setzen den aktuellen Knoten als Vorgänger. Gibt es keinen Knoten mehr zum Auswählen oder ist der ausgewählte Knoten unser gesuchter Knoten, so sind wir fertig.
  3. Bewertung des Knotens: Nachdem wir einen neuen Knoten ausgewählt haben, gehen wir alle noch nicht ausgewählten Knoten Spalte für Spalte durch. Ist der Knoten in der Spalte kein Nachbarknoten, so übernehmen wir die Distanz einfach in die aktuelle Zeile. Ist der Knoten ein Nachbarknoten, so prüfen wir, ob die Distanz über den aktuellen Knoten kleiner ist. Wenn ja, schreiben wir die aktuelle Distanz in die Spalte, wenn nein, übernehmen wir die Distanz aus der vorherigen Zeile. Das machen wir für alle Knoten bzw. alle Spalten. Anschließend gehen wir über zu Auswählen des nächsten Knotens (Punkt 2).

Den kürzesten Weg kann man nun rekonstruieren, in dem man vom letzten ausgewählten Knoten den Vorgänger aus der Tabelle abliest und von diesem Vorgängerknoten wieder den Vorgängerknoten, usw. usf. wodurch man dann den kürzesten Pfad erhält.

Lösungsvorschlag von mnemetz[Bearbeiten]

Basierend auf f.thread:37700

Tabellarische Lösung[Bearbeiten]

Iteration P_{1} P_{2} P_{3} P_{4} P_{5} P_{6} P_{7} P_{8} P_{9} P_{10} Auswahl Vorgänger
0 0 \infty \infty \infty \infty \infty \infty \infty \infty \infty P_{1}
1 3 6 10 1 \infty \infty \infty \infty \infty P_{5} P_{1}
2 3 6 10 \infty \infty \infty 11 \infty P_{2} P_{1}
3 5 11 9 \infty 11 \infty P_{3} P_{2}
4 9 8 \infty \infty P_{7} P_{3}
5 9 11 13 16 P_{4} P_{7}
6 13 10 P_{9} P_{4}
7 12 19 P_{8} P_{9}
8 14 P_{10} P_{8}

Kürzester Weg somit: P_{1} \rightarrow P_{2} \rightarrow P_{3} \rightarrow P_{7} \rightarrow P_{4} \rightarrow P_{9} \rightarrow P_{8} \rightarrow P_{10}

Edit: es gibt noch einen zweiten möglichen kürzesten Weg: P_{1} \rightarrow P_{2} \rightarrow P_{3} \rightarrow P_{4} \rightarrow P_{9} \rightarrow P_{8} \rightarrow P_{10}

tomel: Ich würde eher die zweite Lösung für die korrekte halten, weil im "orangen Buch" auf Seite 69 bei der Beschreibung des Algorithmus in Punkt 2 als Bedingung > und nicht >= angegeben wird. Dh der Vorgänger von P4 bleibt P3, auch wenn er zu denselben Kosten von P7 erreichbar ist, würde ich sagen.

Alternative Lösung[Bearbeiten]

Die Tabelle in der obigen Lösung ist meines Erachtens nicht ganz richtig, da nicht immer der absolut kürzeste, dem System zum Zeitpunkt bekannte, Weg gewählt wird (der auch für die Lösung gesehen sein kann). Ich habe deshalb die Tabelle noch einmal aufgebaut. Das Ergebnis ist zwar das gleiche, aber man kann dann den Algorithmus vielleicht leichter nachvollziehen. Dieses Beispiel ist vor allem deshalb interessant, da es Spezialfälle enthält.

P_1 P_2 P_3 P_4 P_5 P_6 P_7 P_8 P_9 P_{10} Ausgewählter Knoten Vorgängerknoten
0 P_1 -
3 6 10 1 P_5 P_1
3 6 10 11 P_2 P_1
5 10 11 11 P_3 P_2
9 11 8 11 P_7 P_3
9 11 13 11 16 P_4 P_7
11 13 10 16 P_9 P_4
11 12 16 P_6 P_7
12 16 P_8 P_9
14 P_{10} P_8

Rückwärts ausgelesen ist die Lösung demnach P_{10} \leftarrow P_{8} \leftarrow P_{9} \leftarrow P_{4} \leftarrow P_{7} \leftarrow P_{3} \leftarrow P_{2} \leftarrow P_{1} bzw. P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow P_7 \rightarrow P_4 \rightarrow P_9 \rightarrow P_8 \rightarrow P_{10}.

-- Superwayne 20:30, 27. Nov. 2014 (CET)

Anmerkung: Dies ist meiner Meinung nach nicht korrekt. Wenn ich für einen Punkt einen Wert w bekomme und im Laufe des Algorithmus den gleichen Wert w zum selben Punkt ausgehend von einem anderen Vorgänger bekomme, so wird immer nur der erste kürzeste Weg in Betracht gezogen und nicht beide oder der letzte.

graphische Lösung (neu gezeichnet von Bubbleyellow)[Bearbeiten]

219.jpg

Siehe auch:Vorlage:DefinitionVorlage:Extern>

In der folgenden schematisch skizzierten Landkarte sind für eine bestimmte Fracht die Transportkosten zwischen den einzelnen Orten angegeben. Welches ist der billigste Weg vom Ort P_1 zum Ort P_{10}?

Bsp211 1.png

Theorie - Algorithmus von Dijkstra[Bearbeiten]

Siehe Theorie_06.12.2005_Graphentheorie#K.C3.BCrzeste_Wege_.28Dijkstra-Algorithmus.29!

Dijkstra-Kochrezept von Superwayne[Bearbeiten]

Das Ziel des Dijkstra-Algorithmus ist, die kürzeste Distanz von einem Anfangsknoten für einen Endknoten oder alle anderen Knoten zu finden. Am einfachsten ist dafür eine tabellarische Lösung. Für jeden Knoten wird eine Spalte angelegt, sowie eine für den ausgewählten Knoten und den Vorgängerknoten. Mit jeder Zeile "wächst" unser Wissen über den Graph. Eine Zeile ist also eine Iteration, mit der wir mehr wissen über den Graph und seine Zusammensetzung erlangen.

  1. Anfang: Am Anfang wissen wir natürlich noch nichts über den Graph, wir stehen bildlich gesprochen vor dem Anfangsknoten des Graphen und können nur diesen Anfangsknoten sehen. Deshalb legen wir in der Tabelle die erste Zeile an und setzen für den Anfangsknoten die Distanz 0 und für alle anderen Knoten die Distanz unendlich, da wir diese nicht "sehen" können, also noch kein Wissen über diese haben.
  2. Auswählen des nächsten Knotens: Nun müssen wir uns entscheiden, welcher Knoten als nächstes ausgewählt werden soll. Dazu wählen wir den Knoten aus der aktuellen Zeile, der den geringsten Wert (Distanz) aufweist und noch nie ausgewählt wurde. Wir wählen diesen Knoten als Nachfolger aus, d.h. wir vermerken dies in der Spalte Ausgewählter Knoten und setzen den aktuellen Knoten als Vorgänger. Gibt es keinen Knoten mehr zum Auswählen oder ist der ausgewählte Knoten unser gesuchter Knoten, so sind wir fertig.
  3. Bewertung des Knotens: Nachdem wir einen neuen Knoten ausgewählt haben, gehen wir alle noch nicht ausgewählten Knoten Spalte für Spalte durch. Ist der Knoten in der Spalte kein Nachbarknoten, so übernehmen wir die Distanz einfach in die aktuelle Zeile. Ist der Knoten ein Nachbarknoten, so prüfen wir, ob die Distanz über den aktuellen Knoten kleiner ist. Wenn ja, schreiben wir die aktuelle Distanz in die Spalte, wenn nein, übernehmen wir die Distanz aus der vorherigen Zeile. Das machen wir für alle Knoten bzw. alle Spalten. Anschließend gehen wir über zu Auswählen des nächsten Knotens (Punkt 2).

Den kürzesten Weg kann man nun rekonstruieren, in dem man vom letzten ausgewählten Knoten den Vorgänger aus der Tabelle abliest und von diesem Vorgängerknoten wieder den Vorgängerknoten, usw. usf. wodurch man dann den kürzesten Pfad erhält.

Lösungsvorschlag von mnemetz[Bearbeiten]

Basierend auf f.thread:37700

Tabellarische Lösung[Bearbeiten]

Iteration P_{1} P_{2} P_{3} P_{4} P_{5} P_{6} P_{7} P_{8} P_{9} P_{10} Auswahl Vorgänger
0 0 \infty \infty \infty \infty \infty \infty \infty \infty \infty P_{1}
1 3 6 10 1 \infty \infty \infty \infty \infty P_{5} P_{1}
2 3 6 10 \infty \infty \infty 11 \infty P_{2} P_{1}
3 5 11 9 \infty 11 \infty P_{3} P_{2}
4 9 8 \infty \infty P_{7} P_{3}
5 9 11 13 16 P_{4} P_{7}
6 13 10 P_{9} P_{4}
7 12 19 P_{8} P_{9}
8 14 P_{10} P_{8}

Kürzester Weg somit: P_{1} \rightarrow P_{2} \rightarrow P_{3} \rightarrow P_{7} \rightarrow P_{4} \rightarrow P_{9} \rightarrow P_{8} \rightarrow P_{10}

Edit: es gibt noch einen zweiten möglichen kürzesten Weg: P_{1} \rightarrow P_{2} \rightarrow P_{3} \rightarrow P_{4} \rightarrow P_{9} \rightarrow P_{8} \rightarrow P_{10}

tomel: Ich würde eher die zweite Lösung für die korrekte halten, weil im "orangen Buch" auf Seite 69 bei der Beschreibung des Algorithmus in Punkt 2 als Bedingung > und nicht >= angegeben wird. Dh der Vorgänger von P4 bleibt P3, auch wenn er zu denselben Kosten von P7 erreichbar ist, würde ich sagen.

Alternative Lösung[Bearbeiten]

Die Tabelle in der obigen Lösung ist meines Erachtens nicht ganz richtig, da nicht immer der absolut kürzeste, dem System zum Zeitpunkt bekannte, Weg gewählt wird (der auch für die Lösung gesehen sein kann). Ich habe deshalb die Tabelle noch einmal aufgebaut. Das Ergebnis ist zwar das gleiche, aber man kann dann den Algorithmus vielleicht leichter nachvollziehen. Dieses Beispiel ist vor allem deshalb interessant, da es Spezialfälle enthält.

P_1 P_2 P_3 P_4 P_5 P_6 P_7 P_8 P_9 P_{10} Ausgewählter Knoten Vorgängerknoten
0 P_1 -
3 6 10 1 P_5 P_1
3 6 10 11 P_2 P_1
5 10 11 11 P_3 P_2
9 11 8 11 P_7 P_3
9 11 13 11 16 P_4 P_7
11 13 10 16 P_9 P_4
11 12 16 P_6 P_7
12 16 P_8 P_9
14 P_{10} P_8

Rückwärts ausgelesen ist die Lösung demnach P_{10} \leftarrow P_{8} \leftarrow P_{9} \leftarrow P_{4} \leftarrow P_{7} \leftarrow P_{3} \leftarrow P_{2} \leftarrow P_{1} bzw. P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow P_7 \rightarrow P_4 \rightarrow P_9 \rightarrow P_8 \rightarrow P_{10}.

-- Superwayne 20:30, 27. Nov. 2014 (CET)

Anmerkung: Dies ist meiner Meinung nach nicht korrekt. Wenn ich für einen Punkt einen Wert w bekomme und im Laufe des Algorithmus den gleichen Wert w zum selben Punkt ausgehend von einem anderen Vorgänger bekomme, so wird immer nur der erste kürzeste Weg in Betracht gezogen und nicht beide oder der letzte.

graphische Lösung (neu gezeichnet von Bubbleyellow)[Bearbeiten]

219.jpg