文章/答案/技术大牛

发布

社区首页 >问答首页 >边距离相等的生成树中两个顶点的最短路径

问边距离相等的生成树中两个顶点的最短路径
EN

Stack Overflow用户

提问于 2015-03-30 05:47:34

回答 1查看 66关注 0票数 0

我有一个图的生成树，从一个顶点v开始，所有的边都是相同的距离(假设是1)。

如何计算出从v到另一个顶点u的最短路径？

发布于 2015-04-01 06:26:10

在给定的生成树中，无法找到从顶点v到任何顶点u的最短路径。考虑下面的图，其中所有边的成本等于1

显然，v和u之间的最短路径是1。

但是，请考虑上图的以下生成树：

如果我们没有得到这个图，我们就不能知道在v和u之间有一条边。因此，我们只能说有一条从v到u的路径通过长度为2的w。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/29335275

复制

相似问题

问边距离相等的生成树中两个顶点的最短路径EN