TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 211

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!


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 16 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}

graphische Lösung (ohne Erklärung, von mnemetz)[Bearbeiten]

Bsp211 2.png


Bsp211 3.png


Bsp211 4.png