diff options
| author | Paul Jungeblut <paul.jungeblut@gmail.com> | 2016-10-06 20:00:50 +0200 |
|---|---|---|
| committer | Paul Jungeblut <paul.jungeblut@gmail.com> | 2016-10-06 20:00:50 +0200 |
| commit | 461ed24a1542a59e999807c49a4ca05abb6b414a (patch) | |
| tree | 3e4289728e4761bcb52ff252b000b8276d6dce3d /graph/floydWarshall.cpp | |
| parent | 9d121e24674cc1355d27ff35688a205766333928 (diff) | |
Floyd Warshall improvements.
Diffstat (limited to 'graph/floydWarshall.cpp')
| -rw-r--r-- | graph/floydWarshall.cpp | 10 |
1 files changed, 3 insertions, 7 deletions
diff --git a/graph/floydWarshall.cpp b/graph/floydWarshall.cpp index 6b303bb..e9cd526 100644 --- a/graph/floydWarshall.cpp +++ b/graph/floydWarshall.cpp @@ -1,13 +1,9 @@ -// Laufzeit: O(|V|^3) -// Initialisiere mat: mat[i][i] = 0, mat[i][j] = INF falls i & j nicht adjazent, Länge sonst. +// Initialisiere mat: mat[i][i] = 0, mat[i][j] = INF falls i & j nicht +// adjazent, Länge sonst. Laufzeit: O(|V|^3) 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]; - } - } - } - } -} +}}}}} |