在DAG中的两个顶点之间找到最短和最长的路径

Question

给定未加权的DAG（指导的无环图）$ d =（v，a）$和两个顶点$ s $和$ t $，是否可以在多项式时间内找到从$ s $到$ t $的最短路径到$ t $ ？路径长度由边数测量。

我有兴趣在多项式时间内找到可能的路径长度的范围。

ps。，这个问题是stackoverflow问题的重复 达格最长的路径.

Answer 1

对于最短的路径问题，如果我们不关心重量，那就 广度首次搜索 是一种确定的方式。否则 Dijkstra的算法 只要没有负面边缘，就可以使用。

对于最长的道路，你总是可以做 贝尔曼福人 在图表上，所有边缘重量都被否定。回想一下，只要没有负重周期，贝尔曼福音的工作原理就可以使用，因此可以与DAG上的任何重量一起使用。

Answer 2

令$ n = | v（g）| $和$ m = | e（g）| $。令$ w（a to b）$表示边缘$（a to b）$的重量。假设您想找到从$ s $到$ t $的最低路径成本和最高路径成本。

从$ b：= t $开始，执行以下操作：

1. 如果已经访问了$ b $，请返回已经计算的$ min（b）$和$ max（b）$。否则标记为$ b $。

2. 如下确定并记录$ min（b）$和$ max（b）$。

   • 如果$ b = s $，则存储$ min（s）：= max（s）：= 0 $。
   • else设置$$ begin {align*} min（b）＆：= min_ {a to b} bigl [w（a to b） + min（a） bigr] bigr] x max（ b）＆：= max_ {a to b} bigl [w（a to b） + max（a） bigr] end {align*} $$忽略$ min（a）的顶点= max（a）= mathrm {in acccessible} $。当计算最小值和最大值时，一组空的边缘（根本没有入站边缘到$ b $，或全部被忽略）时，设置$ min（b）：= max（b）：= mathrm {incoccessible} $。

您应该能够证明该算法在时间$ o（m）$中运行，忽略了初始化所有顶点变量所需的时间。