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

Question

这里有一道练习题：

证明或举出反例：

(a) 在一个无向图的最小生成树中，两个顶点之间的路径是否一定是最短（最小权重）路径？

(b) 假设该图的最小生成树是唯一的。在一个无向图的最小生成树中，两个顶点之间的路径是否一定是最短（最小权重）路径？

我的回答如下：

(a)

不一定，例如对于图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)，对吗？

- Jackson Tale

---

“MST是唯一的”是如何定义的？ - Deestan

我之所以问是因为如果“unique”的意思仅仅是“存在唯一可能的最小生成树”，那么这个问题就显得平凡和奇怪，因为你已经说了(a)的答案适用于(b)。 - Deestan

http://www.me.utexas.edu/~jensen%20/ORMM/methods/unit/network/subunits/mst_spt/index.html - Goodwine

Answer 1

那么让我们来看一个非常简单的图：

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

这个图的最小生成树由两条边A-B和B-C组成。没有其他一组边构成最小生成树。

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

编辑：

因此，回答问题(b)的答案是否定的，因为存在一条更短的路径，而这条路径不在MST中。

- Kaushik Shankar

Answer 2

关于 (a)，我同意。

关于 (b)，对于一些图形来说，可能会有更多的最小生成树具有相同的权重。考虑一个顶点为a、b、c的圆形C3；权重为a->b=1，b->c=2，a->c=2。这个图形有两个最小生成树，{a-b-c}和{c-a-b}。

尽管如此，你的反例仍然成立，因为在那里最小生成树是唯一的。

- voidengine

Answer 3

广告a)

一个非常简单的可视化如下：

图中的MSP：

从A到C的最短路径：

广告 b)

我猜 MSP 的独特性意味着在一个图中只有一个 MSP。 所以： 首先) 是的，如果边的权重不同，则可能同时存在多个 MST。 在我们的图中，另一个可能的 MSP 将包括 D-C 弧而不是 A-B（作为示例）。 其次) MST 的独特性不影响 a) 的答案。 例如：

- PyFox

Answer 4

MST 不是与起始节点相关联的吗？！
然后他试图从 MST 起始节点获取最短路径。因此，是的，从 A 开始的 MST 给出了最短路径！

- Pedro

---

不完全是这样，最小生成树会尽可能地使用“最少的资源”来到达所有节点，而最短路径将为您提供从“起点”到“目的地”的最短路径。可以这样想：您已经从A走了100英里到B，“B到C”相距50英里，但“A到C”相距120英里。“A->C”肯定比“A->B->C”更短，但您会选择走“B->C”，而不是返回吗？ - Goodwine