algorithm - Floyd 的 Warshall 算法无穷大

Question

我正在实施弗洛伊德 Warshall 算法。我将此算法应用于具有不同顶点的图，其中一些没有链接。我的代码没有得到正确的答案。

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

Answer 1

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