4

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

感谢你们！

4

2 回答 2

6

您可以使用拓扑排序在 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) 时间，这与输入的大小成线性关系。

于 2011-03-24T20:58:35.457 回答
1

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

  • 遍历所有邻居和每个邻居
    • 复制向量
    • 添加邻居
    • 打电话给自己

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

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

剩下的就看你了。

于 2010-11-11T19:47:53.320 回答