\begin{slide}{Kürzeste Wege in Graphen}

(single-source shortest paths)

\begin{itemize}
\item Eingabe: 
  \begin{itemize}
  \item   gerichteter Graph $G=(V,E)$
  \item  Kantengewichte $w: E \to\RR$
  \item Startknoten $s\in V$
  \end{itemize}
\item Ausgabe:
  Funktion $D: V\to \RR$ mit $\forall x\in V:
  D(x)=$ minimales Gewicht eines Pfades von $s$ nach $x$
\end{itemize}

äquivalent: Eingabe ist Matrix 
$w : V\times V \to \RR\cup\{+\infty\}$

bei (von $s$ erreichbaren) negativen Kreisen
gibt es $x$ mit $D(x)=-\infty$

\end{slide}
