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

来源：百度知道 编辑：UC知道 时间：2024/05/16 23:29:40
在看数据结构时，觉得最小生成树就是最短路径，不知道是我理解错了还是本来它俩就是一回事？希望大家帮我分析一下最小生成树与最短路径的区别．
我这里的最短路径是指图中一点到其余各点的路径和．

最小生成树是用和最少的边集将一个图连成任意2点可达，并且这个边集的总长度最小。最短路径是一个图中2个点的最短距离。完全不是一个概念。

那也不一样啊，一点到其余各点的路径和最小，就是一点到其它点的最短路径和。差的太远了。

比如这样一个图(边权已标出)
******4
*****v--v
****5 \ / 3
*******v
****2 / \ 4
*****v v
最小生成树为
****v--v
******/
*****v
****/ \
***v v
总长为4+3+2+4=13

中间那个点到各点的最短路径为5+2+3+4=14
显然不一样啊，反例太多了，举了一种。