graph - 边距离相同的生成树中两个顶点的最短路径

Question

我有一个图的生成树，从顶点 v 开始。所有边的距离都相同（比如说 1）。

我怎样才能算出从 v 到另一个顶点 u 的最短路径？

Answer 1

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

               v
              / \
             /   \
            /     \
           u-------w

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

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

                   v
                    \
                     \
                      \
               u-------w

如果我们没有得到图，我们就无法知道 和 之间有一条v边u。所以，我们只能说有一条从v到u到的路径w，长度为2。