一般定义:节点为 n,边数为 m ,路径权重为 w 求最短路径。
最短路问题
一、单源最短路
按照 w 的正负分为两种情况:
1. 所有边权都是正数
-
朴素版的 Dijkstra 算法,用于稠密图(边数 m 是 n2 级别),时间复杂度为 O(n2)
使用邻接矩阵存储边。
-
堆优化版的 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(n3)
三重循环, d[k][i][j] 表示从 i 出发经过 1,2,…,k 这些点到达 j 点的最短距离。
最小生成树
1. Prim 算法
- 朴素 Prim ,用于稠密图,时间复杂度为 O(n2)
- 堆优化版 Prim,用于稀疏图,时间复杂度为 O(mlogn),优化方式和 Dijkstra 算法很相似。
2. Kruskal 算法
- 时间复杂度为 O(mlogm)
注:实际使用时,如果是稠密图选用朴素 Prim,如果是稀疏图选用 Kruskal 算法。鉴于Kruskal 算法的优势,堆优化版 Prim 算法用的较少。
二分图
定义:图中所有的点分为两边,使得所有边都在集合之间,集合内部没有边。
数论性质:一个图是二分图当且仅当图中不含奇数环。
1. 染色法(用于判定二分图)
由于图中不含有奇数环,所以染色过程中一定没有矛盾。
- 时间复杂度为 O(n+m)
2. 匈牙利算法
- 时间复杂度为 O(mn),实际运行时间一般远小于 O(mn)
注:思路和最大流很相似。