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	$\mathrm{\infty }$	$\mathrm{\infty }$	7	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	b	x
2			11	$\mathrm{\infty }$	6	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	e	b
3			11	$\mathrm{\infty }$		9	$\mathrm{\infty }$	$\mathrm{\infty }$	f	e
4			10	$\mathrm{\infty }$			14	$\mathrm{\infty }$	c	f
5				14			12	$\mathrm{\infty }$	g	c
6								13	y

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

graphische Lösung (ohne Zwischenschritte)