如何在有向无环图中找到两个顶点之间的最大权重路径？

Question

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

谢谢大家！

- Jonathan

---

这似乎是作业。请尝试维基百科：http://en.wikipedia.org/wiki/Longest_path_problem - caveman

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)时间，与输入的大小成线性关系。

- templatetypedef

Answer 2

可以使用递归函数编写简单的暴力算法。 从一个空向量（在C++中为std::vector）开始，插入第一个节点。 然后使用向量作为参数调用递归函数，执行以下操作：

• 循环遍历所有邻居，并对每个邻居执行以下操作：
  • 复制向量
  • 添加邻居
  • 调用自身

还要将总权重作为参数添加到递归函数中，并在每次递归调用中添加权重。

当函数到达终点节点时应停止。然后将总权重与迄今为止的最大权重进行比较（使用全局变量），如果新的总权重更大，则设置最大权重并存储向量。

其余部分由您决定。

- Patrick