加权图中最短路径的数量

Question

这就是问题：给定一个有向图 G=(V,E)，一个源顶点 s $epsilon 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)

*似乎算法会陷入无限循环，也许我可以忽略后缘？（因为最短路径总是简单的）

在那个问题中，图形在这里是未加权的，它是加权的（边）您认为这是正确的吗？谢谢

Answer 1

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]