\documentclass{bschlangaul-aufgabe}
\bLadePakete{graph,mathe}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 5},
  Thematik = {Städte gemischt gerichtet / ungerichtet},
  Referenz = 66112-2004-F.T1-A5,
  RelativerPfad = Examen/66112/2004/03/Thema-1/Aufgabe-5.tex,
  ZitatSchluessel = examen:66112:2004:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Algorithmus von Dijkstra, Adjazenzmatrix},
  EinzelpruefungsNr = 66112,
  Jahr = 2004,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 5,
}

Ein\index{Algorithmus von Dijkstra} \footcite{examen:66112:2004:03}
wichtiges Problem im Bereich der Graphalgorithmen ist die Berechnung
kürzester Wege. Gegeben sei der folgende Graph, in dem Städte durch
Kanten verbunden sind. Die Kantengewichte geben Fahrzeiten an. Außer den
durch Pfeile als nur in eine Richtung befahrbar gekennzeichneten Straßen
sind alle Straßen in beiden Richtungen befahrbar.
\footcite[Aufgabe 1]{aud:pu:6}

\begin{bGraphenFormat}
A: 2 5
B: 3 3
C: 0 3
D: 5 1
E: 4 5
F: 7 1
G: 1 0
H: 6 4
A -- B: 10
A -> C: 70
A -- E: 40
B -- C: 50
B -- D: 90
B -- G: 20
B -- H: 90
C -- G: 20
D -- F: 80
D -- G: 75
E -- H: 5
F -- H: 10
H -> D: 10
\end{bGraphenFormat}

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

\path (A) edge node {10} (B);
\path[->] (A) edge node {70} (C);
\path (A) edge node {40} (E);
\path (B) edge node {50} (C);
\path (B) edge node {90} (D);
\path (B) edge node {20} (G);
\path (B) edge node {90} (H);
\path (C) edge node {20} (G);
\path (D) edge node {80} (F);
\path (D) edge node {75} (G);
\path (E) edge node {5} (H);
\path (F) edge node {10} (H);
\path[->] (H) edge node {10} (D);
\end{tikzpicture}
\end{center}

\begin{enumerate}

%%
% a)
%%

\item Geben Sie zu dem obigen Graphen zunächst eine Darstellung als
Adjazenzmatix an.
\index{Adjazenzmatrix}

\begin{bAntwort}
\[
\begin{blockarray}{ccccccccc}
    &  A &  B &  C &  D &  E &  F &  G &  H \\
\begin{block}{c(cccccccc)}
  A &  * & 10 & 70 &  - & 40 &  - &  - &  - \\
  B & 10 &  * & 50 & 90 &  - &  - & 20 & 90 \\
  C &  - & 50 &  * &  - &  - &  - & 20 &  - \\
  D &  - & 90 &  - &  * &  - & 80 & 75 &  - \\
  E & 40 &  - &  - &  - &  * &  - &  - &  5 \\
  F &  - &  - &  - & 80 &  - &  * &  - & 10 \\
  G &  - & 20 & 20 & 75 &  - &  - &  * &  - \\
  H &  - & 90 &  - & 10 &  5 & 10 &  - &  * \\
\end{block}
\end{blockarray}
\]
\end{bAntwort}

%%
% b)
%%

\item Berechnen Sie nun mit Hilfe des Algorithmus von Dijkstra die
kürzesten Wege vom Knoten $A$ zu allen anderen Knoten.

\begin{bAntwort}
\begin{tabular}{llllllllll}
\bf{Nr.}     & \bf{besucht} & \bf{A}       & \bf{B}       & \bf{C}       & \bf{D}       & \bf{E}       & \bf{F}       & \bf{G}       & \bf{H}       \\
\hline
0            &              & 0            & $\infty$     & $\infty$     & $\infty$     & $\infty$     & $\infty$     & $\infty$     & $\infty$     \\
1            & A            & \bf{0}       & 10           & 70           & $\infty$     & 40           & $\infty$     & $\infty$     & $\infty$     \\
2            & B            & |            & \bf{10}      & 60           & 100          & 40           & $\infty$     & 30           & 100          \\
3            & G            & |            & |            & 50           & 100          & 40           & $\infty$     & \bf{30}      & 100          \\
4            & E            & |            & |            & 50           & 100          & \bf{40}      & $\infty$     & |            & 45           \\
5            & H            & |            & |            & 50           & 55           & |            & 55           & |            & \bf{45}      \\
6            & C            & |            & |            & \bf{50}      & 55           & |            & 55           & |            & |            \\
7            & D            & |            & |            & |            & \bf{55}      & |            & 55           & |            & |            \\
8            & F            & |            & |            & |            & |            & |            & \bf{55}      & |            & |            \\
\end{tabular}

\begin{tabular}{llll}
\bf{nach}                                         & \bf{Entfernung}                                   & \bf{Reihenfolge}                                  & \bf{Pfad}                                         \\
\hline
A  $\rightarrow$  A                               & 0                                                 & 1                                                 &                                                   \\
A  $\rightarrow$  B                               & 10                                                & 2                                                 & A $\rightarrow$ B                                 \\
A  $\rightarrow$  C                               & 50                                                & 6                                                 & A $\rightarrow$ B $\rightarrow$ G $\rightarrow$ C \\
A  $\rightarrow$  D                               & 55                                                & 7                                                 & A $\rightarrow$ E $\rightarrow$ H $\rightarrow$ D \\
A  $\rightarrow$  E                               & 40                                                & 4                                                 & A $\rightarrow$ E                                 \\
A  $\rightarrow$  F                               & 55                                                & 8                                                 & A $\rightarrow$ E $\rightarrow$ H $\rightarrow$ F \\
A  $\rightarrow$  G                               & 30                                                & 3                                                 & A $\rightarrow$ B $\rightarrow$ G                 \\
A  $\rightarrow$  H                               & 45                                                & 5                                                 & A $\rightarrow$ E $\rightarrow$ H                 \\
\end{tabular}
\end{bAntwort}
\end{enumerate}

\end{document}