# Dijkstral

利用贪心的思想，不能处理存在负边权的情况

适用条件：每次从堆顶取出的节点可以保证当前节点已经拥有最小权值

结果：可以得到所有点到起点的最短距离

# 朴素版本：

• 时间复杂度$O(n^2)$
• 用邻接矩阵进行存储
• 外层循环 n - 1 次，每次循环所有结点，找到一个到起点距离最短、不在集合中 (st 为 false) 的结点，将这个结点加入到集合中，并根据这个节点更新其它结点的距离

# 堆优化版：

• 时间复杂度$O(mlogn)$
• 用邻接表（链式前向星）进行存储
• 使用 priority_queue<PII,vector<PII>, greater<PII> ，每次队头的就是距离最小的节点
• 使用标记数组 st，st 为 true 表示该结点加入过队列，即已经得到了该点到原点的最小值
• 先判断距离最小的结点的 st 数组是否为 true，如果是说明已经得到最小值，就跳过后续步骤；否则，修改 st 的值为 true，并用这个节点更新其他节点，更新的节点加入到队列中$\color{red}$

# Bellman_Ford

每次对所有的边进行松弛操作

• 时间复杂度$O(mn)$
• 用结构体进行存储
• 循环 k 次（边数限制为 k），每次利用上一轮的 dist 数组更新这一轮的 dist 数组（所以需要拷贝一份）

# Spfa

优化版的 Bellman_Ford，每次只对上次更新过的点连接的边进行松弛操作

• 宽搜（默认边权全为 1）
  • 时间复杂度$O(mn)$
  • 用邻接表（链式前向星）进行存储
  • 利用队列，因为边权都为 1，所以哪条路先到，哪条就是最短路
• 增强版
  • 时间复杂度$O(mk)$，最坏 k 等于 n
  • 用邻接表（链式前向星）进行存储
  • 使用队列，加入到队列中表示与该节点相连的边待松弛
  • $\color{red}$
  • $\color{red}$
• 利用 spfa 判断负权回路
  • 时间复杂度$O(n)-O(mn)$
  • 如果存在负环，那么一旦进入这个负环，就会一直循环，因为只要在负环里面 dist 就会一直减，所以可以计算每个节点距离最短的路上有几个结点，如果大于等于 n 必定存在负环，因为如果只存在正环或者不存在环，那么最长的应该是 n-1；因为负环不一定是从结点 1 开始的，所以在起始的时候需要把所有结点加入到队列中

# Floyd

多源最短路，直接暴力遍历

• 时间复杂度$O(n^3)$
• 三层循环遍历，最先遍历 k