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

Aus VoWi
Wechseln zu: Navigation, Suche

Bestimmen Sie mit dem Algorithmus von Dijkstra einen kürzesten Weg zwischen den Knoten x und y im folgenden Graphen:

Bsp213 1.png

Theorie - Algorithmus von Dijkstra[Bearbeiten]

Lösungsvorschlag von mnemetz[Bearbeiten]

Tabellarische Lösung[Bearbeiten]

Iteration x b c d e f g y Auswahl Vorgänger
0 0 \infty \infty \infty \infty \infty \infty \infty x
1 4 \infty \infty 7 \infty \infty \infty b x
2 11 \infty 6 \infty \infty \infty e b
3 11 \infty 9 \infty \infty f e
4 10 \infty 14 \infty c f
5 14 12 \infty g c
6 13 13 y

Kürzester Weg somit: x \rightarrow b \rightarrow e \rightarrow f \rightarrow c \rightarrow g \rightarrow y

graphische Lösung (ohne Zwischenschritte)[Bearbeiten]

Bsp213 2.png