Dijkstra算法
$\quad$ 时间复杂度O(n^2)
适用场合：
不存在负权边的最短路问题
算法分析：
dijkstra是每次确定了到一个点的最短距离，再用该点更新到其它点的距离，基于贪心的思想，但是在负权图中局部最优不一定是全局最优
n-1次循环
–>找到未标记的d最小的点
–>标记，松弛它的边
Dijkstra+heap
$\quad$ 时间复杂度O(mlogn)
适用场合：
不存在负权边的最短路问题
算法分析：
使用了小根堆来优化朴素版的dijkstra算法，因为只有当前点的dist变小了才会影响我下一个点的dist的值，因此我们只把dist变小了的点放到小根堆中，并且利用st数组去掉已经操作过的点
用STL中的优先队列实现堆：
while(优先队列非空)
–>队头出队，松弛它的边
–>松弛了的<新距离,点>入队
Bellman-Ford算法
$\quad$ 时间复杂度O(nm)
适用场合：
可存在边权为负数，可存在负权回路，并且有边数限制的最短路
算法分析：
假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新
n-1次循环
–>对所有边松弛
还能再松弛则有负环
注意：back[] 数组是上一次迭代后 dist[] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点
SPFA算法
$\quad$ 时间复杂度一般O(m),最坏O(nm)
适用场合：
可存在负权边，但是不能存在负权回路的最短路问题，且可以判断图是否存在负权回路
算法分析：
在Bellman-Ford算法中，我们对每一个点都进行了n次松弛，但是有很多操作是无用的，我们只要将当前能被松弛的点放入队列即可，并且一个点可以被松弛很多次，因此一个点可以重复入队好多次，这里的st数组用来判断当前点是都还在队列中
判断负权回路：
利用一个数组记录当前点到起始点的距离，要是这个距离>=n-1即说明存在负权回路
while(队非空)
–>队头出队，松弛它的边
–>松弛了且不在队内的点入队
Floyd算法
$\quad$ 时间复杂度一般O(n^3)
适用场合：
多次询问任意两个点之间的最短路径
算法分析：
动态规划思想,dp[i,j,k]表示i到j只经过1~k的点，因此i到j等于i到k加上k到j
初始化d
循环k，循环i，循环j
状态转移方程：dp[i,j,k]=min(dp[i,j,k],dp[i,k,k-1]+dp[k,j,k-1]);
- Dijkstra+heap是用小根堆，每次取出d最小的点，来更新距离，那么这个点来说，最小距离就是当前的d。
- SPFA是用双端队列，每次取出队头，来更新距离，它之后可能还会入队。它是一种动态逼近法，因为每次松弛距离都会减小，所以松弛一定会有结束的。如果一个点入队超过n次就是存在负环。
- 个人认为spfa需要多次入队的原因是存在负权边，当前最优并不一定是全局最优
-----------------------------------------------------------------------------
Prim算法
$\quad$ 时间复杂度O(n^2)
适用场合：
最小生成树问题
算法分析：
Prim算法和dijkstra算法很相似，都是局部最优推出全局最优，在prim中的dist数组存的是距离最小生成树的最短距离，而不是距离1号点的最短距离，因此dist数组存的是当前点到树的最短路径，最终的权值和由n-1个dist相加得到，因此除了第一个点，其他点的dist都不能不存在，不然这个树就不存在；由于prim与dijkstra非常相似，因此prim也可以使用小根堆来优化成O(mlogn)m,但是这个时候使用Kruskal更好
Kruskal算法
$\quad$ 时间复杂度O(mlogm)
适用场合：
最小生成树问题
算法分析：
Kruskal算法是将所有边的权值排序，然后从小到大找到能用上的点就是最小生成树，要是找出的边的数量小于n-1那么就不存在最小生成树，判断当前边是否能用就是判断当前边加上之后会不会产生环，这里使用并查集来解决
