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

Angabe

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

Theorie - Algorithmus von Dijkstra

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

Lösungsvorschlag von mnemetz

Tabellarische Lösung

Iteration	x	b	c	d	e	f	g	y	Auswahl	Vorgänger
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	y

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

graphische Lösung (ohne Zwischenschritte)