algorithm - 使用 Floyd-Warshall 算法计算 2 个顶点之间的路径数

Question

给定一个有向的未加权无环图，我正在尝试采用 Floyd-Warshall 算法来计算 2 个顶点之间的路径数。我的代码目前看起来像这样:

对于 1 到 n 中的所有 k 对于 1 到 n 中的所有 i 对于 1 到 n 中的所有 j Aij = Aij + ( Aik * Akij)。

因此，我没有检查和替换最小距离，而是执行以下操作:

(i,j) 之间没有k 的路径计数 + ( 从i 到k * k * j )

路径数

我的最终数组，应该有任意 2 个顶点之间的路径数。

我无法证明这不会给我两个顶点之间的简单路径的计数，但没有建议在其他地方使用这种方法。

有人可以提供失败的反例吗？

PS:这不是我的作业，只是我捡到的一个编程练习。

Answer 1

在无向无权无环图中，任意两个顶点之间至多有 1 条路径。如果有更多不同的路径，它们将创建一个循环。 (问题被编辑后不相关)

对于有向图，我没有发现您的算法有问题。 this paper中实际上提到了改进的Floyd-Warshall算法的用法。 .它未被广泛使用的原因可能是它的复杂性 - O(n³) 与 this simple approach 的 O(m+n) 相比