首页 文章

加权图中最短路径的数量

提问于
浏览 次
4

这是一个问题：给定有向图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?的副本

在那个问题中，图表在这里没有加权它是加权的（边缘）你认为这是正确的吗？谢谢

algorithm graph

1 回答

  • 1

    如果d [v] == d [u] w（u，v）&&（u，v）不是后备

    条件 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]
    回复于

相关问题