java - Java 中的 Floyd Warshall 具有 15000 个顶点的矩阵

Question

我们正在开展一个小型学校项目，用 Floyd-Warshall 用 java 实现一个算法（我们不能使用另一个）。

该算法运行良好，我们使用成本数组作为 Floyd-Warshall 算法的输入。

老师有 5 个文件要检查，我们传递了 4 个，但第 5 个是一个包含 15 000 个顶点的数组，这意味着一个包含 15 000 * 15 000 个整数的数组。

Java因为内存而拒绝使用它。你知道如何通过这个吗？

谢谢

Answer 1

好吧，算法在最坏情况下的空间复杂度是Θ(n^2)，在最坏情况下你无能为力。

但是，通过使用稀疏矩阵实现而不是二维数组，您可以针对某些特定情况对其进行优化，其中图形非常稀疏，并且有很多对 (v1,v2)，因此没有路径（没有路径！不仅边缘）从v1到v2。

除此之外，您基本上只能增加 jvm 的堆内存。

Answer 2

检查您的数组是否使用了足够大以容纳最大路径长度的最小数据类型。

还要检查您是否使用未装箱的原语（即使用 int 而不是 java.lang.Integer），因为这（可能）更快并且使用更少的内存。