一般定义：节点为 $n$，边数为 $m$ ，路径权重为 $w$ 求最短路径。

最短路问题

一、单源最短路

按照 $w$ 的正负分为两种情况：

1. 所有边权都是正数

• 朴素版的 $Dijkstra$ 算法，用于稠密图（边数 $m$ 是 $n^2$ 级别），时间复杂度为 $O(n^2)$

  使用邻接矩阵存储边。

• 堆优化版的 $Dijkstra$，用于稀疏图（边数 $m$ 是 $n$ 级别），时间复杂度为 $O(mlogn)$

  使用邻接表存储从每个点出发的所有邻边。

2. 存在负权边

• $Bellman-Ford$ 算法，时间复杂度为 $O(nm)$。（边数限制情况下使用）

  求解有边数限制的最短路问题，使用 $Bellman-Ford$ 算法。

  🔺 负权回路：回路权值相加为负数，显然负权回路位于起点到终点的最短路径上就会对结果产生影响。

  $Bellman-Ford$ 算法判断路径中是否存在负权回路：如果第 $n$ 次迭代中，更新了 $dist [\ \ ]$ 数组，说明存在一条长度为 $n + 1$ 的最短路径，根据抽屉原理可以说明存在负权回路。

• $SPFA$ 算法，时间复杂度一般情况下为 $O(m)$，最坏情况为 $O(nm)$。（常用，边权全为正也可用）

  一般而言，$SPFA$ 算法各方面好于 $Bellman-Ford$ 算法（除去有边数限制的情况）。

  $SPFA$ 算法限制：图中不能存在负环。

  $SPFA$ 算法是用队列（堆也可以）优化 $Bellman-Ford$ 算法中距离更新步骤。同时更新其所有出边，不在队列中的需要加入队列。由于 $spfa$ 只会遍历从起点出发可以访问到的点，所以如果终点不可达，即使存在负权边也不会更新终点的距离值 $dist[n]$，最终只需要用 0x3f3f3f3f 来判断起点到终点是否可达。

  🔳 $spfa$ 算法判断负环？

  $cnt[j]$ 表示 $1∼j$ 的最短路上的边数，只要 $cnt[j]$ 大于等于图中的节点数就表示存在负环。

二、多源汇最短路

• $Floyd$ 算法，时间复杂度为 $O(n^3)$

  三重循环， $d[k][i][j]$ 表示从 $i$ 出发经过 $1,2,…,k$ 这些点到达 $j$ 点的最短距离。

最小生成树

1. $Prim$ 算法

• 朴素 $Prim$ ，用于稠密图，时间复杂度为 $O(n^2)$
• 堆优化版 $Prim$，用于稀疏图，时间复杂度为 $O(mlogn)$，优化方式和 $Dijkstra$ 算法很相似。

2. $Kruskal$ 算法

• 时间复杂度为 $O(mlogm)$

注：实际使用时，如果是稠密图选用朴素 $Prim$，如果是稀疏图选用 $Kruskal$ 算法。鉴于$Kruskal$ 算法的优势，堆优化版 $Prim$ 算法用的较少。

二分图

定义：图中所有的点分为两边，使得所有边都在集合之间，集合内部没有边。

数论性质：一个图是二分图当且仅当图中不含奇数环。

1. 染色法（用于判定二分图）

由于图中不含有奇数环，所以染色过程中一定没有矛盾。

• 时间复杂度为 $O(n + m)$

2. 匈牙利算法

• 时间复杂度为 $O(mn)$，实际运行时间一般远小于 $O(mn)$

注：思路和最大流很相似。