这是一个练习：
要么证明以下内容，要么举一个反例：
(a) 无向图的最小生成树中的一对顶点之间的路径一定是最短（最小权重）路径吗？
(b) 假设图的最小生成树是唯一的。无向图的最小生成树中的一对顶点之间的路径是否一定是最短（最小权重）路径？
我的答案是
（一种）
不，例如对于图0、1、2，0-1是4，1-2是2，2-0是5，那么0-2的真实最短路径是5，但是mst是0-1-2 , 在 mst 中, 0-2 是 6
(二)
我的问题来自这个（b）。
我不明白如何whether the MST is unique影响最短路径。
首先，我的理解是，当边的权重不明显时，多个MST可能同时存在，对吧？
其次，即使MST是唯一的，上面（a）的答案仍然适用于（b），对吗？
所以让我们看一个非常简单的图表：
(A)---2----(B)----2---(C)
\ /
---------3----------
该图的最小生成树由两条边A-B和组成B-C。没有其他边集形成最小生成树。
但当然，从A到的最短路径C是A-C，这在 MST 中是不存在的。
编辑
所以要回答 (b) 部分，答案是否定的，因为存在一条不在 MST 中的较短路径。
关于（a），我同意。
关于（b），对于某些图，可能存在更多具有相同权重的最小生成树。考虑一个顶点为 a,b,c 的圆 C3；权重 a->b=1，b->c=2，a->c=2。该图有两个 MST，{abc} 和 {cab}。
尽管如此，你的反例仍然成立，因为 MST 在那里是独一无二的。
一个非常简单的可视化将是：
我猜想 MSP 的唯一性意味着一个图中只有 1 个 MSP MSP。所以：首先）是的，如果边的权重不明显，则可能同时存在多个 MST。在我们的图表中，另一个可能的 MSP 将包括 arc DC 而不是 AB（作为示例）。第二）MST 的唯一性不影响 a）的答案。举个例子：
MST不是和起始节点有关吗？！
然后他试图从 MST 起始节点获取最短路径。因此，是的，最短路径由 MST 给出，从A!