这是一个问题：给定一个有向图G =（V，E），一个源顶点s $εV，我们知道G中的所有循环都具有正权重（> 0）。此外，我们还得到了在Bellman-Ford上运行后的图形，这意味着对于V中的每个v，我们都知道d [v]（从s到v的最短路径）和pi [v]（v的前任）
描述一种算法，以查找V中所有v的从s到v的最短路径的数量。该算法必须以O（V + E）运行
*我们无法编辑在算法上运行的Bellman-Ford
这就是我的想法：我们运行了经过修改的DFS，
算法（G，s）：
1.DFS-Visit(G,s)
2. return count[v] foreach v in V
DFS访问（G，u）：
1.foreach v in Adj[u]
2.if d[v] == d[u] + w(u,v) && (u,v) is not a backedge
3.count[v] = count[v] + 1
4.DFS-visit(G,v)
*似乎算法可能陷入无限循环，也许我可以忽略后端？（因为最短的路径总是很简单的）
*这与“如何在有向图和线性时间中找到两个顶点之间不同的最短路径的数量”不是重复的？
在那个问题中，图形在这里是未加权的（已加权）（边），您认为这是正确的吗？谢谢
if d[v] == d[u] + w(u,v) && (u,v) is not a backedge
条件d[v]==d[u]+w(u,v)在这里是最重要的。如果可以保证这绝不是后盾，而且可以保证您永远不会回到原来的顶点。
确实，假设您回到了曾经去过的顶点。那你有
d[v1]==d[v0]+w(v0,v1)
d[v2]==d[v1]+w(v1,v2)
...
d[v0]==d[vn]+w(vn,v0)
总结一下，我们发现
w(v0,v1)+w(v1,v2)+...+w(vn,v0)==0
那是一个零权重的循环，但是我们被告知没有这样的循环。
因此，该算法永远不会陷入无限循环。此外，如果仅保留满足要求的边d[v]==d[u]+w(u,v)（即使没有，也使图有向），则生成的图将是非循环的。
因此，您可以运行在非循环图中查找多种方式的标准算法。实际上，这就是您已经写的（您的DFS），请注意
count[v] = count[v] + 1
应该
count[v] = count[v] + count[u]
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句