From f5eab7d7e0342ffde45f84243e08fe5a9e2ed036 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Thu, 7 Jan 2016 23:15:32 +0100
Subject: Improvemnts for Floyd Warshall with negative edges/cycles.

---
 graph/graph.tex | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

(limited to 'graph/graph.tex')

diff --git a/graph/graph.tex b/graph/graph.tex
index 8ac82e5..0661ae1 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -30,10 +30,12 @@ Erkennt negative Zyklen.
 \subsubsection{\textsc{Floyd-Warshall}-Algorithmus}
 \lstinputlisting{graph/floydWarshall.cpp}
 \begin{itemize}
-	\item \textsc{Floyd-Warshall} findet auch negative Kreise.
-	Es existiert genau dann ein negativer Kreis, wenn \lstinline{dist[i][i] < 0} ist.
-	\item \textbf{Evtl. überschreibt die Eingabe die Nullen auf der Hauptdiagonalen.}
-	Das ist fast immer ungewollt! 
+	\item Evtl. überschreibt die Eingabe die Nullen auf der Hauptdiagonalen.
+	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.
 \end{itemize}
 
 \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
-- 
cgit v1.2.3

