给定一个有向无加权的acylic图,我试图调整Floyd-Warshall算法来计算2个顶点之间的路径数.我的代码目前看起来像这样:
对于所有k in 1到n,对于所有i in 1到n,对于所有j in 1到n Aij = Aij +(Aik*Akij).
因此,我没有检查和替换最小距离,而是执行以下操作:
(i,j)之间没有k+的路径计数(从*i到k*的路径计数的路径数)kj
我的最终数组应该有任意2个顶点之间的路径数.
我无法证明这不会给我两个顶点之间的简单路径计数,但是没有建议在其他地方使用这种方法.
有人可以提供一个失败的反例吗？
PS:这不是我的作业,而只是我选择的编程练习.