\begin{slide}{Lösungsidee}
  
iterativer Algorithmus mit \emph{Zustand} 
$d : V\to \RR \cup \{+\infty\}$.

\begin{center}
\begin{tabbing}
$d(s) := 0, \forall x\neq s: d(x) := +\infty$ \\
\textbf{while} \= es gibt \= eine Kante $i \stackrel{w_{i,j}}\to j$ mit $d(i)+w_{i,j}< d(j)$ \\
\> $d(j) := d(i) +w_{i,j}$
\end{tabbing}
\end{center}

jederzeit gilt die \emph{Invariante}:
\begin{itemize}\itemsep 2pt
\item $\forall x \in V$: es gibt einen Weg
  von $s$ nach $x$ mit Gewicht $d(x)$
\item $\forall x \in V: D(x) \le d(x)$.
\end{itemize}

verbleibende Fragen:
\begin{itemize} \itemsep 2pt
\item Korrektheit (falls Termination)
\item Auswahl der Kante (aus mehreren Kandidaten)
\item Termination, Laufzeit
\end{itemize}

\end{slide}
