我们正在一个小型学校项目上，用Floyd-Warshall在Java中实现一种算法(不能再使用其他算法)。
该算法运行良好，我们使用成本数组作为Floyd-Warshall算法的输入。
老师有5个文件要检查，我们通过了4个，但是第5个是具有15000个顶点的数组，这意味着有15000 * 15000个整数的数组。
Java由于内存原因拒绝使用它。你知道如何通过这个吗？
谢谢
最佳答案
好吧，算法在最坏情况下的空间复杂度是Θ(n^2)，在最坏情况下您无能为力。
但是，通过使用sparse matrix实现而不是2-d数组，您可以针对某些特定情况对其进行优化，在这种情况下，图形非常稀疏，并且有很多对(v1，v2)，因此没有路径(没有路径!不仅是v1到v2的edge)。
除此之外，您基本上只能使用increase the jvm's heap memory。