From 461ed24a1542a59e999807c49a4ca05abb6b414a Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 6 Oct 2016 20:00:50 +0200 Subject: Floyd Warshall improvements. --- graph/graph.tex | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'graph/graph.tex') diff --git a/graph/graph.tex b/graph/graph.tex index a3ae298..77ee874 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -28,12 +28,10 @@ Erkennt negative Zyklen. \subsubsection{\textsc{Floyd-Warshall}-Algorithmus} \lstinputlisting{graph/floydWarshall.cpp} \begin{itemize} - \item Evtl. überschreibt die Eingabe die Nullen auf der Hauptdiagonalen. - Nur negative Werte sollten die Nullen überschreiben. + \item Nur negative Werte sollten die Nullen überschreiben. \item Von parallelen Kanten sollte nur die günstigste gespeichert werden. - \item Knoten \lstinline{i} liegt genau dann auf einem negativen Kreis, wenn \lstinline{dist[i][i] < 0} ist. - \item Ein u-v-Pfad existiert nicht, wenn \lstinline{dist[u][v] == INF}. - \item Gibt es einen Knoten \lstinline{c}, sodass \lstinline{dist[u][c] != INF && dist[c][v] != INF && dist[c][c] < 0}, wird der u-v-Pfad beliebig kurz. + \item \lstinline{i} liegt genau dann auf einem negativen Kreis, wenn \lstinline{dist[i][i] < 0} ist. + \item Wenn für \lstinline{c} gilt, dass \lstinline{dist[u][c] != INF && dist[c][v] != INF && dist[c][c] < 0}, wird der u-v-Pfad beliebig kurz. \end{itemize} \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} -- cgit v1.2.3