在看数据结构时,觉得最小生成树就是最短路径,不知道是我理解错了还是本来它俩就是一回事?希望大家帮我分析一下最小生成树与最短路径的区别．我这里的最短路径是指图中一点到其余各

Question

在看数据结构时,觉得最小生成树就是最短路径,不知道是我理解错了还是本来它俩就是一回事?希望大家帮我分析一下最小生成树与最短路径的区别．
我这里的最短路径是指图中一点到其余各点的路径和．

Answer 1

最小生成树是用和最少的边集将一个图连成任意2点可达,并且这个边集的总长度最小.最短路径是一个图中2个点的最短距离.完全不是一个概念.
那也不一样啊,一点到其余各点的路径和最小,就是一点到其它点的最短路径和.差的太远了.
比如这样一个图(边权已标出)
v
****/ \
***v v
总长为4+3+2+4=13
中间那个点到各点的最短路径为5+2+3+4=14
显然不一样啊,反例太多了,举了一种.