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

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	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	x
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 }$	${\displaystyle }$	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				13	y

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

graphische Lösung (ohne Zwischenschritte)