From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 graph/floydWarshall.cpp | 31 ++++++++++++++++++++++++-------
 1 file changed, 24 insertions(+), 7 deletions(-)

(limited to 'graph/floydWarshall.cpp')

diff --git a/graph/floydWarshall.cpp b/graph/floydWarshall.cpp
index e9cd526..fb6263e 100644
--- a/graph/floydWarshall.cpp
+++ b/graph/floydWarshall.cpp
@@ -1,9 +1,26 @@
-// Initialisiere mat: mat[i][i] = 0, mat[i][j] = INF falls i & j nicht
-// adjazent, Länge sonst. Laufzeit: O(|V|^3)
+vector<vector<ll>> dist; // Entfernung zwischen je zwei Punkten.
+vector<vector<int>> pre;
+
 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];
+	pre.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) {
+				pre[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++) {
+				if (dist[i][j] > dist[i][k] + dist[k][j]) {
+					dist[i][j] = dist[i][k] + dist[k][j];
+					pre[i][j] = pre[i][k];
 }}}}}
+
+vector<int> getPath(int u, int v) {
+	//return dist[u][v]; // Pfadlänge u -> v
+	if (pre[u][v] < 0) return {};
+	vector<int> path = {v};
+	while (u != v) path.push_back(u = pre[u][v]);
+	return path; //Pfad u -> v
+}
-- 
cgit v1.2.3