algorithm - 在树中的多条路径之间找到共同的最短边

Question

给定一个无向的加权树（N 个节点，N-1 个双向边，不一定是二叉树）。输入将是一些节点之间的简单路径（从开始节点到最低共同祖先到结束节点），例如 1->4、2->10。找到所有给定路径的公共（属于）最短边。

Answer 1

Basically, have a count at each node for number of paths crossing it. After setting up these counts, process the tree and find the shortest common edge. A common edge would be one where the counts of each end-point would be equal to the number of paths.

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