algorithm - 最小生成树和最短路径树的区别

Question

这是一个练习:

Either prove the following or give a counterexample:

(a) Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?

(b) Suppose that the minimum spanning tree of the graph is unique. Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?

我的答案是

(一)

不是，比如对于图0,1,2，0-1是4，1-2是2，2-0是5，那么0-2的真实最短路径是5，但是mst是0- 1-2，在mst中，0-2是6

(b)

我的问题出在这个 (b) 上。

我不明白MST 是否唯一 会如何影响最短路径。

首先，我的理解是，当边的权重不明显时，可能同时存在多个MST，对吧？

其次，即使 MST 是唯一的，上面 (a) 的答案仍然适用于 (b)，对吗？

Answer 1

让我们看一个非常简单的图表:

(A)---2----(B)----2---(C)
 \                    /
  ---------3----------

此图的最小生成树由两条边 A-B 和 B-C 组成。没有其他边集形成最小生成树。

当然，从A到C的最短路径是A-C，这在MST中是不存在的。

编辑

所以要回答第 (b) 部分，答案是否定的，因为存在一条不在 MST 中的较短路径。