Dijkstra-Algorithmus, kürzester Weg

Question

Frage: Bestimmen Sie tabellarisch mit Hilfe des Dijkstra-Algorithmus die kürzesten Wege von Knoten A zu allen anderen Knoten.

Kann mir jemand helfen, ist die Tabelle richtig ausgefüllt? Und wenn ja, kann mir jemand es nochmal erklären?

Code:

Text erkannt:

Notation (Wichtigi):
Permanent gelabelt: Zahl mit * \( 2 . \) B. 1 *
Temporar gelabelt: Zahi z.B. 1
Weg von der Quelle unbekannt: \( u \)
Geben Sie Ihre Losung in die folgende Tabelle ein:
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline Schritt & & \( A \) & 8 & C & D & E \\
\hline 1 & Entf: & \( 0^{*} \) & 7 & 4 & 10 & 4 \\
\hline 2 & Entf: & \( 0^{*} \) & 7 & \( 4^{*} \) & 10 & 4 \\
\hline 3 & Entf: & \( 0^{*} \) & 7 & \( 4^{*} \) & \( 5^{*} \) & \( U \) \\
\hline 4 & Entf: & \( 0^{*} \) & \( 6^{*} \) & \( 4^{*} \) & \( 5^{*} \) & \( U \) \\
\hline 5 & Entf: & \( 0^{*} \) & \( 6^{*} \) & \( 4^{*} \) & \( 5^{*} \) & \( 16^{*} \) \\
\hline
\end{tabular}

Answer 1

Wir starten bei Knoten A im 1. Schritt schreiben alle Kosten zu den erreichbaren Knoten (B=7,C=4,D=10) auf, alle nicht erreichbaren Knoten mit u (manchmal auch unendlich), A haben wir besucht also Sternchen an die 0.

Wir gehen zum Knoten mit den niedrigsten Kosten von A aus also C, hier kommen wir zu A,D und E, A haben wir bereits besucht (*) zu D kommen wir mit weiteren Kosten von 1 also 4+1 = 5 besser als 10 überschreiben, zu E mit Kosten 4+20=24. Sternchen an C=4.

Weiter zu D da geringste Kosten von allen nicht besuchten Knoten, von D kommen wir zu A,B,C und E, besucht haben wir A und C bereites, wir ermitteln die Kosten von D zu C = 5+1 = 6 kleiner als der bisheriger wert 7 also überschreiben. Von D zu E = 5 + 23 = 28 schlechterer Wert als 24 also dabei belassen, Sternchen an D=5.

Wir gehen zu B mit bisher Kosten von 6 (Über A,C und D) von hier aus kommen wir an A,D und E, an A und D haben wir Sternchen also berechnen wir die Kosten für E mit 6+10=16, besser als bisheriger Wert also überschreiben.

Wir besuchen E es gibt keine nicht besuchten Knoten also Sternchen an E=16.