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}{（先判断st，再判断距离）}\)

Bellman_Ford

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

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

Spfa

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

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

Floyd

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

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