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

$\mathrm{\infty }$

$\mathrm{\infty }$

$\mathrm{\infty }$

$\mathrm{\infty }$

$\mathrm{\infty }$

$\mathrm{\infty }$

$\mathrm{\infty }$

$\mathrm{\infty }$

$\mathrm{\infty }$

$P_1$

1

3

6

10

1

$\mathrm{\infty }$

$\mathrm{\infty }$

$\mathrm{\infty }$

$\mathrm{\infty }$

$\mathrm{\infty }$

$P_5$

$P_1$

2

3

6

10

$\mathrm{\infty }$

$\mathrm{\infty }$

$\mathrm{\infty }$

11

$\mathrm{\infty }$

$P_2$

$P_1$

3

5

11

9

$\mathrm{\infty }$

11

$\mathrm{\infty }$

$P_3$

$P_2$

4

9

8

$\mathrm{\infty }$

$\mathrm{\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\to P_2\to P_3\to P_7\to P_4\to P_9\to P_8\to P_{10}$

Edit: es gibt noch einen zweiten möglichen kürzesten Weg: $P_1\to P_2\to P_3\to P_4\to P_9\to P_8\to P_{10}$

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