algorithm - 加权图中最短路径的数量

这是问题:
给定一个有向图 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)

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

*这不是重复的
How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

在那个问题中，图在这里是未加权的，它是加权的(边)
你认为这是正确的吗？
谢谢

最佳答案

d[v]==d[u]+w(u,v) 条件在这里是最重要的。 If 保证这永远不是一个backedge，而且，它保证你永远不会回到你去过的顶点。

事实上，假设你回到了你去过的顶点。那么你有

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]

关于algorithm - 加权图中最短路径的数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30423802/