Improvemnts for Floyd Warshall with negative edges/cycles.

1 files changed, 7 insertions, 5 deletions

diff --git a/graph/floydWarshall.cpp b/graph/floydWarshall.cpp
index 30d463a..6b303bb 100644
--- a/graph/floydWarshall.cpp
+++ b/graph/floydWarshall.cpp
@@ -1,10 +1,12 @@
 // Laufzeit: O(|V|^3)
-// Initialize adjmat: adjmat[i][i] = 0, adjmat[i][j] = INF if no edge is between i and j, length otherwise.
+// Initialisiere mat: mat[i][i] = 0, mat[i][j] = INF falls i & j nicht adjazent, Länge sonst.
 void floydWarshall() {
-	for (k = 0; k < NUM_VERTICES; k++) {
-		for (i = 0; i < NUM_VERTICES; i++) {
-			for (j = 0; j < NUM_VERTICES; j++) {
-				if (adjmat[i][k] + adjmat[k][j] < adjmat[i][j]) adjmat[i][j] = adjmat[i][k] + adjmat[k][j];
+	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];
+				}
 			}
 		}
 	}