algorithm - ツリー内の複数のパス間の共通の最短エッジを見つける

Question

無向で加重されたツリー (N ノード、N-1 双方向エッジ、必ずしもバイナリ ツリーではない) が与えられます。入力は、1->4、2->10 のように、いくつかのノード間の単純なパス (開始ノードから最も低い共通の祖先、終了ノードまで) になります。与えられたすべてのパスに共通する (所属する) 最短のエッジを見つけます。

Answer 1

基本的に、各ノードで、ノードを通過するパスの数をカウントします。これらのカウントを設定した後、ツリーを処理し、最短の共通エッジを見つけます。共通のエッジは、各エンドポイントの数がパスの数と等しくなるエッジです。

i = 0

// set up counts
for each path p
  for each node n on path
    if n.count != i // early path stop condition, past common ancestor
      break // go to next path
    n.count++
  i++

current = root
shortestEdge = null

// find shortest edge
while true
  for each child c of current
    if c.count == pathCount
      shortestEdge = shortest(shortestEdge, edge(current, c))
      current = c
      break // out of for-loop
    else
      stop // stop while-loop