algorithm - 如何在具有重复节点值的 n 叉树中找到最短路径？

Question

这是一个例子：

     0
     1 
   2   3 
          2

我正在寻找 2 和 3 之间的最短路径，即等于 1。

标签： algorithmtreeshortest-path

Answer 1

首先创建指向每个出现的 2 和 3 的指针集，每个指针保持一个整数，显示它到目前为止移动的总距离。在树的每个节点上留出空间，说明是否已被每种类型的指针看到，如果是，则该指针当时累积的距离以及指针的来源。

重复地将每个指针向上移动一步，增加它的距离。查看它到达的树节点上的注释。如果这是同一类型，并且距离大于指针的距离，则更换注释。如果这是同一类型且距离不更大，则相同类型的两个指针发生碰撞，您可以放下第二个指针。如果它是不同类型的，则您有可能的最短路径。

继续前进，直到每个指针都在顶部，或者每个指针都至少行进到找到的最短路径，因为在那之后找到的任何路径都必须比找到的最短路径长。

在最坏的情况下，我们一直工作到最后，我们遍历整个树，但每种类型只遍历一次，因为一个类型的指针到达一个已经被另一个相同类型的指针传递的节点会看到到它的距离节点小于自己的距离并停止。因此，最坏情况的成本与树的大小呈线性关系。