如何在DAG中找到两个顶点之间的最大权重路径？

Question

在具有非负加权边的DAG G中,如何找到G中两个顶点之间的最大权重路径？

感谢你们!

Answer 1

您可以使用拓扑排序在O(n + m)时间(其中n是节点数和m边数)中解决此问题.首先在反向图上进行拓扑排序,以便所有节点的排序方式使得在访问所有子节点之前不会访问任何节点.

现在,我们将使用从该节点开始的最高权重路径的权重标记所有节点.这是基于以下递归观察完成的:

• 从汇聚节点(没有传出边缘的任何节点)开始的最高权重路径的权重为零,因为从该节点开始的唯一路径是该节点的长度为零的路径.
• 从任何其他节点开始的最高权重路径的权重由通过跟随到节点的输出边缘形成的任何路径的最大权重给出,然后从该节点获取最大权重路径.

因为我们对节点进行了反向拓扑排序,所以我们可以按顺序访问所有节点,以确保如果我们尝试跟踪边缘并查找该节点端点上最重路径的成本,我们就已经有了计算从该节点开始的最大权重路径.这意味着一旦我们具有反向拓扑排序顺序,我们就可以将以下算法应用于该顺序中的所有节点:

1. 如果节点没有输出边缘,则将从该节点开始的最重路径的权重(表示为d(u))记录为零.
2. 否则,对于离开当前节点u的每个边(u,v),计算l(u,v)+ d(v),并将d(u)设置为以这种方式获得的最大值.

一旦我们完成了这一步,我们就可以在所有节点上进行最后一次传递,并返回任何节点获得的最高值d.

可以如下分析该算法的运行时间.计算拓扑排序可以使用许多不同的方法在O(n + m)时间内完成.然后,当我们扫描每个节点和每个节点的每个传出边缘时,我们只访问每个节点和边缘一次.这意味着我们在节点上花费O(n)时间,在边缘花费O(m)时间.最后,我们花费O(n)时间对元素进行最后一次传递以找到最高权重路径,这需要O(n).这给出了总的O(n + m)时间,其在输入的大小上是线性的.