\documentclass{bschlangaul-aufgabe}
\bLadePakete{graph}
\begin{document}
\bAufgabenMetadaten{
  Titel = {9. Aufgabe},
  Thematik = {Graph a-g},
  Referenz = 66115-2013-H.T2-A9,
  RelativerPfad = Examen/66115/2013/09/Thema-2/Aufgabe-9.tex,
  ZitatSchluessel = examen:66115:2013:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Algorithmus von Dijkstra},
  EinzelpruefungsNr = 66115,
  Jahr = 2013,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 9,
}

Gegeben\index{Algorithmus von Dijkstra} \footcite{examen:66115:2013:09}
sei der unten stehende gerichtete Graph $G=(V, E)$ mit positiven
Kantenlingen $l(e)$ für jede Kante $e \in E$. Kanten mit Doppelspitzen
können in beide Richtungen durchlaufen werden.

\begin{bGraphenFormat}
a: 0 -1
b: 10 -1
c: 5.6 6
d: 3 1
e: 7 1
f: 5 4
g: 5 2
a -- b: 11
a -- c: 25
a -> d: 2
a -> e: 8
b -> c: 3
c -- f: 5
d -- f: 9
d -> e: 7
e -> b: 1
e -> g: 1
g -> f: 2
d -> g: 3
c -> e: 1
e -- f: 1
\end{bGraphenFormat}

\begin{tikzpicture}[li graph]
\node (a) at (0,-1) {a};
\node (b) at (10,-1) {b};
\node (c) at (5.6,6) {c};
\node (d) at (3,1) {d};
\node (e) at (7,1) {e};
\node (f) at (5,4) {f};
\node (g) at (5,2) {g};

\path (a) edge node {11} (b);
\path (a) edge node {25} (c);
\path[->] (a) edge node {2} (d);
\path[->] (a) edge node {8} (e);
\path[->] (b) edge node {3} (c);
\path[->] (c) edge node {1} (e);
\path (c) edge node {5} (f);
\path[->] (d) edge node {7} (e);
\path (d) edge node {9} (f);
\path[->] (d) edge node {3} (g);
\path[->] (e) edge node {1} (b);
\path (e) edge node {1} (f);
\path[->] (e) edge node {1} (g);
\path[->] (g) edge node {2} (f);
\end{tikzpicture}

% Im Original ohne Nummerierung
\begin{enumerate}

%%
%
%%

\item In welcher Reihenfolge werden die Knoten von $G$ ab dem Knoten $a$
durch den Dijkstra-Algorithmus bei der Berechnung der kürzesten Wege
endgültig bearbeitet?

\begin{bAntwort}
\begin{tabular}{lllllllll}
\bf{Nr.}     & \bf{besucht} & \bf{a}       & \bf{b}       & \bf{c}       & \bf{d}       & \bf{e}       & \bf{f}       & \bf{g}       \\
\hline
0            &              & 0            & $\infty$     & $\infty$     & $\infty$     & $\infty$     & $\infty$     & $\infty$     \\
1            & a            & \bf{0}       & 11           & 25           & 2            & 8            & $\infty$     & $\infty$     \\
2            & d            & |            & 11           & 25           & \bf{2}       & 8            & 11           & 5            \\
3            & g            & |            & 11           & 25           & |            & 8            & 7            & \bf{5}       \\
4            & f            & |            & 11           & 12           & |            & 8            & \bf{7}       & |            \\
5            & e            & |            & 9            & 12           & |            & \bf{8}       & |            & |            \\
6            & b            & |            & \bf{9}       & 12           & |            & |            & |            & |            \\
7            & c            & |            & |            & \bf{12}      & |            & |            & |            & |            \\
\end{tabular}
\end{bAntwort}

%%
%
%%

\item Berechnen Sie die Länge des kürzesten Weges von $a$ zu jedem
Knoten.

\begin{bAntwort}
siehe oben
\end{bAntwort}

%%
%
%%

\item Geben Sie einen kürzesten Weg von $a$ nach $c$ an.

\begin{bAntwort}
a $\rightarrow$ d $\rightarrow$ g $\rightarrow$ f $\rightarrow$ c
\end{bAntwort}
\end{enumerate}

\end{document}