From f5eab7d7e0342ffde45f84243e08fe5a9e2ed036 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 7 Jan 2016 23:15:32 +0100 Subject: Improvemnts for Floyd Warshall with negative edges/cycles. --- graph/floydWarshall.cpp | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) (limited to 'graph/floydWarshall.cpp') 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]; + } } } } -- cgit v1.2.3