MST VS SSSP VS SPT - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

最小生成树Minimum Spanning Tree 最短路径Single Source Shortest Path 最短路径树Shortest Path Tree

	最小生成树Minimum Spanning Tree	单源最短路径Single Source Shortest Path	最短路径树Shortest Path Tree
定义	最小生成树能够保证整个图的所有路径之和最小，但不能保证任意两点之间是最短路径	最短路径是从一点出发，到达目的地的路径最小	以一个结点为根，然后根结点到其他所有结点的距离最短，然后形成了一棵树，把不必要的边删除
总结	遇到求所有路径之和最小的问题用最小生成树&并查集解决	遇到求两点间最短路径问题的用最短路径，例如从一个城市到另一个城市最短的路径问题
区别	最小生成树构成后所有的点都被连通	最短路径只要到达目的地走的是最短的路径即可，与所有的点连不连通没有关系

• 一个图中的最短路径树可能是最小生成树，反之亦然，两者没有特别联系