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

Answer 1

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.

Answer 2

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.