mzuenni tests

1 files changed, 27 insertions, 0 deletions

diff --git a/content/graph/floydWarshall.cpp b/content/graph/floydWarshall.cpp
new file mode 100644
index 0000000..df096c2
--- /dev/null
+++ b/content/graph/floydWarshall.cpp
@@ -0,0 +1,27 @@
+vector<vector<ll>> dist; // Entfernung zwischen je zwei Punkten.
+vector<vector<int>> next;
+
+void floydWarshall() {
+	next.assign(sz(dist), vector<int>(sz(dist), -1));
+	for (int i = 0; i < sz(dist); i++) {
+		for (int j = 0; j < sz(dist); j++) {
+			if (dist[i][j] < INF) {
+				next[i][j] = j;
+	}}}
+
+	for (int k = 0; k < sz(dist); k++) {
+		for (int i = 0; i < sz(dist); i++) {
+			for (int j = 0; j < sz(dist); j++) {
+				// only needed if dist can be negative
+				if (dist[i][k] == INF || dist[k][j] == INF) continue;
+				if (dist[i][j] > dist[i][k] + dist[k][j]) {
+					dist[i][j] = dist[i][k] + dist[k][j];
+					next[i][j] = next[i][k];
+}}}}}
+
+vector<int> getPath(int u, int v) {
+	if (next[u][v] < 0) return {};
+	vector<int> path = {u};
+	while (u != v) path.push_back(u = next[u][v]);
+	return path; //Pfad u -> v
+}