最短路径和最小生成树

学习数据结构的时候一直忘记了区分这两个，现在正是用博客记录一下。

一、区别

• 最小生成树能保证整个拓扑图的 所有路径权值之和最小 ，但是不能保证 任意两点间是最短路径
• 最短路径是从 一点 出发，到达目的地的路径权值和最小

二、实现算法

最短路径

Dijkstra算法

1. 指定一个节点为初始点，将其看作一个 集合S ，剩余的点看作 另一个集合U
2. 根据初始点，求出到其他点的距离 d[i]（若相邻，则为边的权值；若不相邻，则为 ∞ ）
3. 选择最小的d[i]，并将其加入集合S，在U中去除它，暂时用x标记
4. 再根据x，更新跟x相邻点y的d[y]的值：d[y] = min{ d[y], d[x] + w[x][y] }，则个操作有可能把距离调小，也有可能没变化，因而称为松弛操作
5. 重复3，4两步操作，直至集合S包括所有的点，即集合U为空集时，求得初始点到其他所有点的最短路径

• 时间复杂度 O(e*logv)

最小生成树

Prim算法

1. 选择任意节点为起始点，加入点集合V，初始化边集合E为空
2. 选取集合V中的点到剩余节点的最小权值边，加入E，然后把该边连接的节点加入V
3. 重复以上步骤，直至集合V包括所有的节点
4. 所求的 {V，E} 就是最小生成树

• 时间复杂度取决于图的存储方式
  • 邻接矩阵 O(v^2)
  • 邻接表 O(e*logv)

Kruskal算法

1. 新建图 {V,E}，V有原来图的所有顶点，而 E为空集，因而每个节点自成一个连通分量
2. 在原图的边中选择权值最小的边
   1. 若该边依附的顶点落在新建图中 不同的连通分量，则将此边加入E
   2. 否则舍去此边，寻找下一条权值最小的边
3. 以此类推，直至新建图 所有的节点在同一连通分量

• 时间复杂度 O(eloge)