TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 326

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

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Theorie - Algorithmus von Dijkstra

• Siehe TU_Wien:Mathematik_1_UE_(diverse)/Theorie_WS05/06.12.2005_Graphentheorie#K.C3.BCrzeste_Wege_.28Dijkstra-Algorithmus.29!
• Eine Erklärung des Algorithmus unter Verwendung einer Tabelle gibt es im Video Der Dijkstra-Algorithmus auf YouTube.

Lösungsvorschlag von mnemetz

Tabellarische Lösung

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$	Fehler beim Parsen (⧼math_empty_tex⧽): {\displaystyle }	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)