Floyd Warshall

3 files changed, 12 insertions, 0 deletions

diff --git a/graph/floydWarshall.cpp b/graph/floydWarshall.cpp
new file mode 100644
index 0000000..ee56441
--- /dev/null
+++ b/graph/floydWarshall.cpp
@@ -0,0 +1,8 @@
+//initialize adjmat, adjmat[i][i] = 0, adjmat[i][j] = INF if no edge is between i and j
+for (k = 0; k < MAX_V; k++) {
+	for (i = 0; i < MAX_V; i++) {
+		for (j = 0; j < MAX_V; j++) {
+			if (adjmat[i][k] + adjmat[k][j] < adjmat[i][j]) adjmat[i][j] = adjmat[i][k] + adjmat[k][j];
+		}
+	}
+}
\ No newline at end of file
diff --git a/graph/graph.tex b/graph/graph.tex
index 2bf395c..8d01e97 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -10,6 +10,10 @@ Kürzeste Pfade in Graphen ohne negative Kanten.
 Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen.
 \lstinputlisting{graph/bellmannFord.cpp}
 
+\subsubsection{\textsc{Floyd-Warshall}-Algorithmus}
+Alle kürzesten Pfade im Graphen.
+\lstinputlisting{graph/floydWarshall.cpp}
+
 \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
 \lstinputlisting{graph/scc.cpp}
 
diff --git a/tcr.pdf b/tcr.pdf
index 07e4ceb..af23bcc 100644
--- a/tcr.pdf
+++ b/tcr.pdf