\documentclass{bschlangaul-aufgabe}
\bLadePakete{graph}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Dijkstra-Algorithmus},
  Thematik = {Graph A-I},
  Referenz = AUD.Graphen.Dijkstra.Graph-A-I,
  RelativerPfad = Module/30_AUD/90_Graphen/10_Dijkstra/Aufgabe_Graph-A-I.tex,
  ZitatSchluessel = aud:e-klausur,
  ZitatBeschreibung = {Aufgabe 4},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Algorithmus von Dijkstra},
}

Führen Sie auf dem gegebenen Graphen die Suche nach der kürzesten
Distanz aller Knoten zum Startknoten $A$ mit dem Algorithmus von
Dijkstra durch. Tragen Sie die Abarbeitungsreihenfolge, den
unmittelbaren Vorgängerknoten, sowie die ermittelte kürzeste Distanz für
jeden Knoten ein! Bei gleichen Distanzen arbeiten Sie die Knoten in
lexikalischer Reihenfolge ab.
\index{Algorithmus von Dijkstra}
\footcite[Aufgabe 4]{aud:e-klausur}

\begin{bGraphenFormat}
A: 1 4
B: 3 5
C: 3 3
D: 0 2
E: 5 5
F: 5 1
G: 3 0
H: 6 3
I: 8 4
A -- B: 2
A -- C: 5
A -- D: 2
B -- C: 3
B -- E
C -- D: 3
C -- E
C -- F
C -- H
D -- G: 2
E -- I: 7
F -- G: 2
F -- H: 3
H -- I
\end{bGraphenFormat}

\begin{center}
\begin{tikzpicture}[li graph]
\node (A) at (1,4) {A};
\node (B) at (3,5) {B};
\node (C) at (3,3) {C};
\node (D) at (0,2) {D};
\node (E) at (5,5) {E};
\node (F) at (5,1) {F};
\node (G) at (3,0) {G};
\node (H) at (6,3) {H};
\node (I) at (8,4) {I};

\path (A) edge node {2} (B);
\path (A) edge node {5} (C);
\path (A) edge node {2} (D);
\path (B) edge node {3} (C);
\path (B) edge (E);
\path (C) edge node {3} (D);
\path (C) edge (E);
\path (C) edge (F);
\path (C) edge (H);
\path (D) edge node {2} (G);
\path (E) edge node {7} (I);
\path (F) edge node {2} (G);
\path (F) edge node {3} (H);
\path (H) edge (I);
\end{tikzpicture}
\end{center}

\begin{bAntwort}
\begin{tabular}{lllllllllll}
\bf{Nr.}     & \bf{besucht} & \bf{A}       & \bf{B}       & \bf{C}       & \bf{D}       & \bf{E}       & \bf{F}       & \bf{G}       & \bf{H}       & \bf{I}       \\
\hline
0            &              & 0            & $\infty$     & $\infty$     & $\infty$     & $\infty$     & $\infty$     & $\infty$     & $\infty$     & $\infty$     \\
1            & A            & \bf{0}       & 2            & 5            & 2            & $\infty$     & $\infty$     & $\infty$     & $\infty$     & $\infty$     \\
2            & B            & |            & \bf{2}       & 5            & 2            & 3            & $\infty$     & $\infty$     & $\infty$     & $\infty$     \\
3            & D            & |            & |            & 5            & \bf{2}       & 3            & $\infty$     & 4            & $\infty$     & $\infty$     \\
4            & E            & |            & |            & 4            & |            & \bf{3}       & $\infty$     & 4            & $\infty$     & 10           \\
5            & C            & |            & |            & \bf{4}       & |            & |            & 5            & 4            & 5            & 10           \\
6            & G            & |            & |            & |            & |            & |            & 5            & \bf{4}       & 5            & 10           \\
7            & F            & |            & |            & |            & |            & |            & \bf{5}       & |            & 5            & 10           \\
8            & H            & |            & |            & |            & |            & |            & |            & |            & \bf{5}       & 6            \\
9            & I            & |            & |            & |            & |            & |            & |            & |            & |            & \bf{6}       \\
\end{tabular}

\noindent
\begin{tabular}{llll}
\bf{nach}                                                                         & \bf{Entfernung}                                                                   & \bf{Reihenfolge}                                                                  & \bf{Pfad}                                                                         \\
\hline
A  $\rightarrow$  A                                                               & 0                                                                                 & 0                                                                                 &                                                                                   \\
A  $\rightarrow$  B                                                               & 2                                                                                 & 2                                                                                 & A $\rightarrow$ B                                                                 \\
A  $\rightarrow$  C                                                               & 4                                                                                 & 5                                                                                 & A $\rightarrow$ B $\rightarrow$ E $\rightarrow$ C                                 \\
A  $\rightarrow$  D                                                               & 2                                                                                 & 3                                                                                 & A $\rightarrow$ D                                                                 \\
A  $\rightarrow$  E                                                               & 3                                                                                 & 4                                                                                 & A $\rightarrow$ B $\rightarrow$ E                                                 \\
A  $\rightarrow$  F                                                               & 5                                                                                 & 7                                                                                 & A $\rightarrow$ B $\rightarrow$ E $\rightarrow$ C $\rightarrow$ F                 \\
A  $\rightarrow$  G                                                               & 4                                                                                 & 6                                                                                 & A $\rightarrow$ D $\rightarrow$ G                                                 \\
A  $\rightarrow$  H                                                               & 5                                                                                 & 8                                                                                 & A $\rightarrow$ B $\rightarrow$ E $\rightarrow$ C $\rightarrow$ H                 \\
A  $\rightarrow$  I                                                               & 6                                                                                 & 9                                                                                 & A $\rightarrow$ B $\rightarrow$ E $\rightarrow$ C $\rightarrow$ H $\rightarrow$ I \\
\end{tabular}

\end{bAntwort}
\end{document}