1

我有一棵树，其中每条边都被分配了一个权重（一个可以是正数或负数的实数）。我需要一种算法来找到最大总权重的简单路径（即路径中边的权重之和最大的简单路径）。路径开始或结束的节点没有限制。

我有一个可能的算法，但我不确定它是否有效，我正在寻找一个证据。这里是：

  1. 选择任意节点u并运行 DFS( u ) 以找到从u开始的最大权重简单路径。让 ( u , v ) 成为这条路径。
  2. 运行 DFS( v ) 以找到从v开始的最大权重简单路径。让这条路径是（v，z）。

那么 ( v , z ) 是最大权重的简单路径。该算法在图的大小上是线性的。谁能告诉我它是否有效，如果有效，请提供证据？

注意：对于具有循环的一般图，最长路径问题是 NP-Hard。但是，我在这里只考虑树。

4

3 回答 3

1

如果您允许负权重，请考虑以下示例：

a<->b : -5000
a<->c : 1
b<->d : 1
b<->e : 1

最长的路径是d<->b<->e，长度为 2

随便挑一个开始。DFS 返回距离为 1 的c。第二个 DFS 返回距离为 1 的a。但是a<->c不是最长的路径。

于 2013-01-15T13:41:51.680 回答
0

如果您确定图中没有循环，我会尝试以下操作：

function findLongestPath(tree)
begin

   all_paths := {}

   for each neighbour 
      all_paths.append(create_path(this_node, findLongestPath(three - current_node))

   sort_descending(all_paths)
   return  all_paths[0];
end

该算法可以进一步优化以仅存储最佳路径而不是一组（无需存储所有可能的路径和排序）。

于 2013-01-15T15:28:34.703 回答
0

这是它有效的证明。该算法找到一对节点 x0,y0 使得 max_x d(x,x0) = max_y d(x0,y)（即 x0 和 y0 是彼此最远的节点）。对于任何这样的对，d(x0,y0) 是直径。证明：设 x*,y* 为两个节点 st d(x*,y*) 为直径。存在节点 r 和 s，因此路径看起来像 x0--r--s--y0 和 x*--r--s--y*。假设 d(x0,y0) < d(x*,y*)，则 d(x0,y*) > d(x0,y0) 或 d(y*,x0) > d(y0,x0)，矛盾x0 和 y0 是彼此最远的点这一事实。因此 d(x0,y0)=d(x*,y*)

于 2013-01-15T14:46:59.040 回答