我正在学习一门在线算法入门课程。
在最后评估中,有一个问题如下:
在Andrew Goldberg采访中描述的甲骨文的最短路径中,
每个节点都有一个标签,它是
网络及其到这些节点的距离。这些列表包含
财产:
(1)对于网络中的任意一对节点(x,y),它们的列表将具有
至少有一个共同的节点z
(2)从x到y的最短路径将通过z。给定一个图G
这是一个平衡的二叉树,对图进行预处理以创建
每个节点的标签。注意每个标签中列表的大小
对于大小为n的图形,不应大于logn。
The full question can be found here.
考虑到平衡二叉树的约束和大小不应大于log n的提示,直观地看,特定节点的标签将由其所有父节点组成(如果不是叶节点,则可以选择自身)。
但是,问题中的一些附加讲师注释补充道:
写下你的解决方案来处理加权图。注意测试
假设,所有的边都有一个重量-这不是特别的
很有趣。
所以我的问题是:
二叉树中两个节点之间的最短路径如何受路径是否具有权重的影响?
当然,在二叉树中,两个节点之间的最短路径是唯一的简单路径,并且不受任何权重的影响?
(除非权重可以为负数,并且路径不必很简单,在这种情况下没有最短路径?)
我的基本解决方案与问题中提供的简单测试一起工作,但未能通过自动评分器,自动评分器没有给出任何反馈。
我显然有点误会,但是…

最佳答案

好吧,我想我最初的反应和明显的答案是正确的:
正权重不会影响二叉树中两个节点之间的最短路径。
另一方面,与简单地将节点之间的“距离”计算为跳数相比,权重显然会影响二叉树中两个节点之间的最短“距离”。
这就是udacity教学的目的。
似乎使用加权二叉树的这条指令只是为了使代码能够正确地自动分级,这依赖于使用标签来计算准确的最短“距离”(受权重影响),而不是不受权重影响的最短路径(节点列表)。
一旦我修改了我的算法,考虑到这一点并输出正确的距离,它就通过了分级机。

关于algorithm - 平衡二叉树中两个节点之间的最短路径如何受到路径“权重”的影响?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/25544442/

10-08 22:16
查看更多