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

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}$?

Theorie - Algorithmus von Dijkstra

Siehe TU_Wien:Mathematik_1_UE_(diverse)/Theorie_WS05/06.12.2005_Graphentheorie!

Lösungsvorschlag von mnemetz

Basierend auf f.thread:37700

Tabellarische Lösung

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)