Floyd 的 warshall 算法无限

Question

我正在努力实现 floyd warshall 算法。我将此算法应用于具有不同顶点的图形，其中一些顶点没有链接。我的代码没有得到正确答案。

从一个顶点到另一个顶点生成的最终路径有时会包含一条不存在的边。我认为我的错误来自于我将无穷大与无穷大进行比较。我目前这样做： 我假设一个大整数将代表无穷大，例如10000。当我遇到10000 > 10000 + n这样的情况时该怎么办？ n < 10000

Answer 1

最长的可能有效路径的长度可以为 (n - 1) * 1000。因此，"infinity" 必须严格大于该值。只要 2 * infinity 适合您用来存储距离的类型，就不需要特别处理它。