平衡二叉树中两个节点之间的最短路径如何受到路径“权重”的影响？

Question

我正在使用Udacity进行在线介绍算法课程。

在最后的评估存在的问题如下：

在安德鲁·戈德堡的采访中描述的最短路径甲骨文， 每个节点都有一个标签，这是在其他一些节点的列表 网络及其到这些节点的距离。这些列表具有 属性是：

（1）对于任何一对网络中的节点（X，Y）的，他们的列表将在 至少一个节点Z共同

（2）最短从x到y的路径将通过z。给定一个平衡二叉树图G ，对图进行预处理，为每个节点创建这样的 标签。请注意，对于大小为n的图形，每个标签 中列表的大小不应大于log n。

The full question can be found here.

给定一个平衡二叉树的约束和提示，大小不应超过数N时，直观看来，对于一个特定节点的标签将包括其所有的父母（如果不是叶子，也可以选择本身）。

然而，在这个问题一些额外的教练笔记补充说：

写您的解决方案，加权图形工作。请注意，测试 给出，所有的边缘有一个权重 - 这并不是特别有趣。

所以我的问题是：

如何二叉树两个节点之间的最短路径由路径是否具有重量或不会受到影响？

当然，在二叉树中，两个节点之间的最短路径是唯一的简单路径，并且不受任何权重的影响？ （除非权重可以是负数，并且路径不必简单，在这种情况下没有最短路径）

我的基本解决方案与问题中提供的简单测试一起工作，但未能通过自动不给予反馈的平地机。

我显然误解的东西，但什么......

Answer 1

好了，我想我最初的反应和明显的答案是正确的：

正权不能影响最短路径在二叉树中的两个节点之间。

在另一方面，权重明显做影响二叉树的最短“距离”两个节点之间相比，计算简单的跳数节点之间的“距离”。

这就是udacity指令得到的。 似乎这条使用加权二叉树的指令只是简单地启用对依赖于使用标签的代码进行正确的自动分级来计算确切的最短'距离'（受重量影响），而不是最短路径（节点列表）不是。

一旦我修改了我的算法，将其考虑在内并输出正确的距离，它就通过了平地机。