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

Aus VoWi
Wechseln zu: Navigation, Suche

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