From 53e7f12d828bb94c05d2b6c4e04d61de9482c426 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 3 Dec 2015 01:12:26 +0100 Subject: Improving graoh chapter. --- graph/floydWarshall.cpp | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) (limited to 'graph/floydWarshall.cpp') diff --git a/graph/floydWarshall.cpp b/graph/floydWarshall.cpp index f5c950d..30d463a 100644 --- a/graph/floydWarshall.cpp +++ b/graph/floydWarshall.cpp @@ -1,8 +1,11 @@ -//initialize adjmat, adjmat[i][i] = 0, adjmat[i][j] = INF if no edge is between i and j, length otherwise -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]; +// Laufzeit: O(|V|^3) +// Initialize adjmat: adjmat[i][i] = 0, adjmat[i][j] = INF if no edge is between i and j, length otherwise. +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]; + } } } -} \ No newline at end of file +} -- cgit v1.2.3