\begin{slide}{Laufzeit}

\usetikzlibrary{arrows}

exponentiell viele Relaxations-Schritte:

\begin{center}
\begin{tikzpicture}
  [node distance=5cm,auto,>=stealth,thick]
    \node (s) {s};
    \node (p) [right of=s] {p};
    \node (q) [right of=p] {q};
    \node (t) [right of=q] {t};
    \path[->] (s) edge [bend right] node [below] {4} (p);
    \path[->] (p) edge [bend right] node [below] {2} (q);
    \path[->] (q) edge [bend right] node [below] {1} (t);
    \path[->] (s) edge [bend left] node {0} (p);
    \path[->] (p) edge [bend left] node {0} (q);
    \path[->] (q) edge [bend left] node {0} (t);
\end{tikzpicture}
\end{center}

besser:
\begin{itemize}\itemsep 0pt
\item Bellman-Ford (polynomiell)

  for $i$ from $1$ to $|V|$: jede Kante $e\in E$ einmal entspannen

  dann testen, ob alle Kanten entspannt sind. \\
  (d. h. $d(j) \ge  d(i) + w_{i,j}$)

  Wenn nein, dann existiert negativer Kreis. (Beweis?)
\item Dijkstra 
  (schneller, aber nur bei Gewichten $\ge 0$ korrekt)
\end{itemize}


\end{slide}
