使用Floyd-Warshall算法来计算2个顶点之间的路径数量 [英] Using Floyd-Warshall algorithm to count number of paths between 2 vertices

问题描述

给定一个定向的未加权的acylic图，我试图调整Floyd-Warshall算法来计算2个顶点之间的路径数量。我的代码目前看起来像这样：

所有k在1到n
所有我在1到n
所有j在1到n
Aij = Aij +（Aik * Akij）。

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

没有<$（ i ， j ）之间的路径计数c $ c> k +（从 i 到 k 的路径数）*来自 k * j ）

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

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

有人可以提供一个计数器例子吗？

PS ：这不是我的家庭作业，而仅仅是我选择的编程练习。

在未加权的acylic图中，任何两个顶点之间至多有一条路径。如果有更多不同的路径，他们会创建一个循环。 （编辑问题后不相关）

对于有向图，我没有看到你的算法有问题。实际上，在这篇论文中提到了改进的Floyd-Warshall算法的使用。。它没有被广泛使用的原因可能是它的复杂性 - O（n ³ ）与O（m + n）相比较这个简单的方法

Given an directed unweighted acylic graph, I am trying to adapt Floyd-Warshall algorithm to count the number of paths between 2 vertices. My code currently looks like this:

for all k in 1 to n for all i in 1 to n for all j in 1 to n Aij = Aij + ( Aik * Akij).

Therefore, instead of checking and replacing for min distance, I am doing the following:

Count of paths between (i,j) without k + ( Count of paths from i to k * Count of paths from k * j )

My final array, should have the number of paths between any 2 vertices.

I am not able to prove that this does not give me the count of simple paths between 2 vertices, but there are no suggestions to use this approach elsewhere.

Can someone provide a counter example where this fails?

PS: This is not my homework, but just a programming exercise I picked up.

解决方案

In an undirected unweighted acylic graph there's at most 1 path between any two vertices. If there were more distinct paths, they would create a cycle. (not relevant after question was edited)

For directed graphs, I don't see a problem with your algorithm. The usage of modified Floyd-Warshall algorithm is actually mentioned in this paper. The reason it's not used widely is probably its complexity - O(n³) compared to O(m+n) of this simple approach

这篇关于使用Floyd-Warshall算法来计算2个顶点之间的路径数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！