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开始的路径计数）kj

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

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

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

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

score 5 · Accepted Answer

~~在无向无权无环图中，任意两个顶点之间最多有 1 条路径。如果有更多不同的路径，它们就会形成一个循环。~~ （编辑问题后不相关）

对于有向图，我认为您的算法没有问题。修改后的 Floyd-Warshall 算法的使用实际上在本文中有所提及。它没有被广泛使用的原因可能是它的复杂性 - O(n ³ ) 与这种简单方法的 O(m+n) 相比

score 2 · Accepted Answer

在循环图的情况下，您不能使用直接的 Floyd-Warshall 算法来做到这一点，因为计算简单路径需要您跟踪您去过的地方。动态规划假设正在计算的状态只是递归中状态的函数，在这种情况下并非如此。

但是，我不明白为什么这不起作用。但是为什么要使用 Floyd-Warshall 只计算两个顶点（只使用 DFS 或 BFS）。

2 回答 2