From 4cc304e57566d149582d974cdaf4a7f724c6b5c1 Mon Sep 17 00:00:00 2001
From: pjungeblut <paul.jungeblut@gmail.com>
Date: Sun, 23 Nov 2014 22:59:10 +0100
Subject: Floyd Warshall

---
 graph/floydWarshall.cpp | 8 ++++++++
 graph/graph.tex         | 4 ++++
 2 files changed, 12 insertions(+)
 create mode 100644 graph/floydWarshall.cpp

(limited to 'graph')

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}
 
-- 
cgit v1.2.3