Floyd Warshall improvements.

3 files changed, 6 insertions, 12 deletions

diff --git a/graph/floydWarshall.cpp b/graph/floydWarshall.cpp
index 6b303bb..e9cd526 100644
--- a/graph/floydWarshall.cpp
+++ b/graph/floydWarshall.cpp
@@ -1,13 +1,9 @@
-// Laufzeit: O(|V|^3)
-// Initialisiere mat: mat[i][i] = 0, mat[i][j] = INF falls i & j nicht adjazent, Länge sonst.
+// Initialisiere mat: mat[i][i] = 0, mat[i][j] = INF falls i & j nicht
+// adjazent, Länge sonst. Laufzeit: O(|V|^3)
 void floydWarshall() {
 	for (k = 0; k < MAX_V; k++) {
 		for (i = 0; i < MAX_V; i++) {
 			for (j = 0; j < MAX_V; j++) {
 				if (mat[i][k] != INF && mat[k][j] != INF && mat[i][k] + mat[k][j] < mat[i][j]) {
 					mat[i][j] = mat[i][k] + mat[k][j];
-				}
-			}
-		}
-	}
-}
+}}}}}
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)}
diff --git a/tcr.pdf b/tcr.pdf
index 130bdca..bdd8adc 100644
--- a/tcr.pdf
+++ b/tcr.pdf