『算法-ACM 竞赛-图论』最短路径生成树与最小生成树

虽然放在一起，但是他们两个除了都是树之外没有一点关系。
最短路径生成树，就是 ROOT 根节点到达任意点距离最短的路径所构成的树，就是最短路径生成树。我画两个图给大家理解。
最短路径生成树

最小生成树

这时候大家会发现，最短路径生成树不就是求完最短路之后，路径所构成的树吗，其实就是这样的。但是这里要明白一点，最短路径生树不唯一。我们举一个最简单的例子，如下图：

只选 2-3 权值的边构成一颗最短路径生成树，之选 2 5 构成一颗最短路径生成树。
最短路径生树的详解：戳这里
最小生成树的详解：戳这里
生成树相关：戳这里