Floyd Warshall in Java with a matrix of 15000 vertex

Question

We are working on a small school project to implement a algorithm in java with Floyd-Warshall (we can't use another one).

The algorithm is working well, and we use a cost Array as input for the Floyd-Warshall Algo.

The teacher has 5 file to check, we passed 4 but the 5th is an array with 15 000 vertex that's mean an array of 15 000 * 15 000 integers.

Java refuse to use it because of the memory. Do u have any idea how to pass this ?

Thx

[Just increase your heap memory of the jvm](http://stackoverflow.com/q/1565388/572670) 15k*15k is over 200 MB — amit, May 28 '14 at 15:46
Ah forget to say that we gonna launch it on the teacher computer and he doesn't want that we touch on his parameter :( — Guillaume Rebmann, May 28 '14 at 15:52
Floyd algo complexity is O(N^3), for N=15000 it is too big, your teacher will not get the answer in his life :) — juver, May 29 '14 at 07:34

score 3 · Accepted Answer · edited May 23 '17 at 12:27

3

Well, the algorithm's space complexity at worst case is Θ(n^2), there is not much you can do for worst case.

However, by using a sparse matrix implementation instead of a 2-d array, you could optimize it for some specific cases, where the graph is very sparse, and there are a lot of pairs (v1,v2) such that there is no path (no path! not only edge) from v1 to v2.

Other than that, you could basically only increase the jvm's heap memory.

edited May 23 '17 at 12:27

Community

1
1

answered May 28 '14 at 16:12

amit

175,853
27
231
333

+1 And the sparse matrix approach also works in the (admittedly unlikely) case when a non-zero value is the overwhelmingly most frequent one. Although come to think about it, this is exactly such a case if the graph isn't fully connected. – biziclop May 28 '14 at 16:18

score 1 · Answer 2 · answered May 28 '14 at 17:43

Check that your array is using the smallest possible data type that is large enough to hold the maximum path length.

Also check that you are using an unboxed primitive (i.e. use int instead of java.lang.Integer) as this is (probably) faster and uses less memory.

Floyd Warshall in Java with a matrix of 15000 vertex

2 Answers2