\documentclass{bschlangaul-aufgabe}
\bLadePakete{graph}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Flugverbindung zwischen sieben Städten},
  Thematik = {Städte A-F},
  Referenz = AUD.Graphen.Dijkstra.Staedte-A-F,
  RelativerPfad = Module/30_AUD/90_Graphen/10_Dijkstra/Aufgabe_Staedte-A-F.tex,
  ZitatSchluessel = aud:ab:6,
  ZitatBeschreibung = {Seite 1, Aufgabe 1: Dijkstra},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Algorithmus von Dijkstra},
}

Nehmen Sie an, es gibt sieben Städte A, B, C, D, E, F und G. Sie wohnen
in der Stadt A und möchten zu jeder der anderen Städte die preiswerteste
Flugverbindung finden (einfach ohne Rückflug). Sie sind dazu bereit,
beliebig oft umzusteigen. Folgende Direktflüge stehen Ihnen zur
Verfügung:
\index{Algorithmus von Dijkstra}
\footcite[Seite 1, Aufgabe 1: Dijkstra]{aud:ab:6}

\begin{center}
\begin{tabular}{l|r}
Städte & Preis \\\hline
A $\leftrightarrow$ B & 300 € \\
A $\leftrightarrow$ F & 1000 € \\
B $\leftrightarrow$ C & 1000 € \\
B $\leftrightarrow$ D & 700 € \\
B $\leftrightarrow$ E & 300 € \\
B $\leftrightarrow$ G & 1000 € \\
C $\leftrightarrow$ F & 200 € \\
D $\leftrightarrow$ F & 400 € \\
E $\leftrightarrow$ F & 300 € \\
F $\leftrightarrow$ G & 300 € \\
\end{tabular}
\end{center}

\noindent
Der Preis p in einer Zeile

\begin{center}
\begin{tabular}{l|r}
Städte & Preis \\\hline
x $\leftrightarrow$ y & p \\
\end{tabular}
\end{center}

\noindent
gilt dabei sowohl für einen einfachen Flug von x nach y als auch für
einen einfachen Flug von y nach x. Bestimmen Sie mit dem Algorithmus von
Dijkstra (führen Sie den Algorithmus händisch durch!) die Routen und die
Preise für die preiswertesten Flugverbindungen von der Stadt A zu jeder
der anderen Städte.

\begin{bGraphenFormat}
A: 6 6
B: 8 4
C: 8 2
D: 6 0
E: 1 0
F: 0 4
G: 2 6
A -- B: 300
A -- F: 1000
B -- C: 1000
B -- D: 700
B -- E: 300
B -- G: 1000
C -- F: 200
D -- F: 400
E -- F: 300
F -- G: 300
\end{bGraphenFormat}

Als TikZ-Umgebung

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

\path (A) edge node {300} (B);
\path (A) edge node {1000} (F);
\path (B) edge node {1000} (C);
\path (B) edge node {700} (D);
\path (B) edge node {300} (E);
\path (B) edge node {1000} (G);
\path (C) edge node {200} (F);
\path (D) edge node {400} (F);
\path (E) edge node {300} (F);
\path (F) edge node {300} (G);
\end{tikzpicture}

\noindent
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
Schritt & besuchte Knoten & A & B & C & D & E & F & G \\\hline\hline

Init &
& % besuchte Knoten
0 & % A
$\infty$ & % B
$\infty$ & % C
$\infty$ & % D
$\infty$ & % E
$\infty$ & % F
$\infty$ \\\hline% G

1 &
\textbf{A} & % besuchte Knoten
0 & % A
\textbf{300,A} & % B
$\infty$ & % C
$\infty$ & % D
$\infty$ & % E
1000,F & % F
$\infty$ \\\hline% G

2 &
A,\textbf{B} & % besuchte Knoten B 300
0 & % A
| & % B
1300,B & % C
1000,B & % D
\textbf{600,B} & % E
1000,F & % F
1300,B \\\hline% G

3 &
A,B,\textbf{E} & % besuchte Knoten E 600
0 & % A
| & % B
1300,B & % C
1000,B & % D
| & % E
\textbf{900,E} & % F
1300,B \\\hline% G

4 &
A,B,E,\textbf{F} & % besuchte Knoten F 900
0 & % A
| & % B
1100,F & % C
\textbf{1000,B} & % D
| & % E
| & % F
1200,F \\\hline% G

5 &
A,B,E,F,\textbf{D} & % besuchte Knoten D 1000
0 & % A
| & % B
\textbf{1100,F} & % C
| & % D
| & % E
| & % F
1200,F \\\hline% G

6 &
A,B,E,F,D,\textbf{C} & % besuchte Knoten C 1100
0 & % A
| & % B
| & % C
| & % D
| & % E
| & % F
\textbf{1200,F} \\\hline% G

7 &
A,B,E,F,D,C,\textbf{G} & % besuchte Knoten G 1200
0 & % A
| & % B
| & % C
| & % D
| & % E
| & % F
| \\\hline% G
\end{tabular}

\noindent
\begin{tabular}{|l|l|}
\hline
Städte & Preis\\\hline\hline
A $\rightarrow$ B & 300 \\\hline
A $\rightarrow$ B $\rightarrow$ E $\rightarrow$ F $\rightarrow$ C & 1100 \\\hline
A $\rightarrow$ B $\rightarrow$ D & 1000 \\\hline
A $\rightarrow$ B $\rightarrow$ E & 600 \\\hline
A $\rightarrow$ B $\rightarrow$ E $\rightarrow$ F & 900 \\\hline
A $\rightarrow$ B $\rightarrow$ E $\rightarrow$ F $\rightarrow$ G & 1200 \\\hline
\end{tabular}
\end{document}