1

各エッジに重み（正または負の実数）が割り当てられているツリーがあります。最大総重みの単純なパス（つまり、パス内のエッジの重みの合計が最大になる単純なパス）を見つけるためのアルゴリズムが必要です。パスが開始または終了するノードに制限はありません。

可能なアルゴリズムはありますが、それが機能するかどうかはわかりません。証拠を探しています。ここにあります：

  1. 任意のノードuを選択し、 DFS（u ）を実行して、 uで始まる最大重みの単純パスを見つけます。（u、v）をこのパスとします。
  2. DFS（v ）を実行して、 vで始まる最大重みの単純パスを見つけます。このパスを（v、z）とします。

その場合、（v、z）は最大重みの単純なパスです。このアルゴリズムは、グラフのサイズが線形です。誰かがそれが機能するかどうか教えてもらえますか？もしそうなら、証拠を与えてください？

注：サイクルのある一般的なグラフの場合、最長パスの問題はNP困難です。ただし、ここでは木のみを考慮します。

4

3 に答える 3

1

負の重みを許可する場合は、次の例を検討してください。

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

最長のパスはd<->b <-> eで、長さは2です。

開始するために任意にを選択します。DFSは距離1のcを返します。2番目のDFSは距離1のaを返します。ただし、a<->cは最長のパスではありません。

于 2013-01-15T13:41:51.680 に答える
0

これが機能することの証明です。アルゴリズムは、max_x d（x、x0）= max_y d（x0、y）となるノードx0、y0のペアを検出します（つまり、x0とy0は互いに最も遠いノードです）。このようなペアの場合、d（x0、y0）は直径です。証明：x *、y*を2つのノードとします。std（x *、y *）は直径です。パスがx0--r--s--y0およびx*-r--s--y*のように見えるようなノードrおよびsが存在します。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 に答える
0

If you are sure there are no cycles in the graph, I would try something like:

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

The algorithm can be further optimised to store just the best path instead of a set (removes the need of storing all possible paths and sorting).

于 2013-01-15T15:28:34.703 に答える