这一节讲的是最短路。
常见的最短路问题,一般分为两大类:
在最短路问题中,源点也就是起点,汇点也就是终点。
单源最短路,指的是求一个点,到其他所有点的最短距离。(起点是固定的,单一的)
根据是否存在权重为负数的边,又分为两种情况
所有边的权重都是正数
通常有两种算法
朴素Dijkstra
时间复杂度O(n2),其中n是图中点的个数,m是边的个数
堆优化版的Dijkstra
时间复杂度O(mlogn)
两者孰优孰劣,取决于图的疏密程度(取决于点数n,与边数m的大小关系)。当是稀疏图(n和m是同一级别)时,可能堆优化版的Dijkstra会好一些。当是稠密图时(m和n2是同一级别),使用朴素Dijkstra会好一些。
存在权重为负数的边
通常有两种算法
Bellman-Ford
时间复杂度O(nm)
SPFA
时间复杂度一般是O(m),最差O(nm),是前者的优化版,但有的情况无法使用SPFA,只能使用前者,比如要求最短路不超过k条边,此时只能用Bellman-Ford
求多个起点到其他点的最短路。(起点不是固定的,而是多个)
Floyd算法(时间复杂度O(n3))
最短路问题的核心在于,把问题抽象成一个最短路问题,并建图。图论相关的问题,不侧重于算法原理,而侧重于对问题的抽象。
Dijkstra基于贪心,Floyd基于动态规划,Bellman-Ford基于离散数学。
算法的选用:通常来说,单源最短路的,如果没有负权重的边,用Dijkstra,有负权重边的,通常用SPFA,极少数用Bellman-Ford;多源最短路的,用Floyd。
假设图中一共有n个点,下标为1~n。下面所说的某个点的距离,都是指该点到起点(1号点)的距离。
算法步骤如下,用一个集合s
来存放最短距离已经确定的点。
初始化距离,d[1] = 0, d[i] = +∞
。即,将起点的距离初始化为0,而其余点的距离当前未确定,用正无穷表示。
循环
每次从距离已知的点中,选取一个不在s
集合中,且距离最短的点(这一步可以用小根堆来优化),遍历该点的所有出边,更新这些出边所连接的点的距离。并把该次选取的点加入到集合s
中,因为该点的最短距离此时已经确定。
当所有点都都被加入到s
中,表示全部点的最短距离都已经确定完毕
注意某个点的距离已知,并不代表此时这个点的距离就是最终的最短距离。在后续的循环中,可能用一条更短距离的路径,去更新。
练习题:acwing - 849: Dijkstra求最短路 I
题解(C++)
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 510; const int INF = 0x3f3f3f3f; // 正无穷 int g[N][N]; // 稠密图采用邻接矩阵存储 int d[N]; // 距离 int n, m; bool visited[N]; int dijkstra() { d[1] = 0; // 每次 for(int i = 1; i <= n; i++) { //找到一个距起点距离最小的点 int t = 0; // d[0]未被使用, 其值一直是 INF for(int j = 1; j <= n; j++) { if(!visited[j] && d[j] < d[t]) { t = j; } } if(t == 0) break; // 未找到一个点, 提前break // 找到该点 visited[t] = true; // 放入集合s // 更新其他所有点的距离 for(int i = 1; i <= n; i++) { d[i] = min(d[i], d[t] + g[t][i]); } } if(d[n] == INF) return -1; else return d[n]; } int main() { // 初始化 memset(d, 0x3f, sizeof d); memset(g, 0x3f, sizeof g); scanf("%d%d", &n, &m); while(m--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); g[x][y] = min(g[x][y], z); // 重复边只需要保留一个权重最小的即可 } printf("%d", dijkstra()); return 0; }
题解(Java)
import java.util.Arrays; import java.util.Scanner; /** * @Author yogurtzzz * @Date 2021/6/25 9:01 * * 稠密图, 使用邻接矩阵存储 **/ public class Main { static final int INF = 0x3f3f3f3f; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n, m; n = scanner.nextInt(); m = scanner.nextInt(); int[][] g = new int[n + 1][n + 1]; // 图的邻接矩阵存储 for(int i = 0; i < n + 1; i++) { for (int j = 0; j < n + 1; j++) g[i][j] = INF; // 初始化全部距离为正无穷 } while(m-- > 0) { int x, y, z; x = scanner.nextInt(); y = scanner.nextInt(); z = scanner.nextInt(); g[x][y] = Math.min(g[x][y], z); // 解决重边, 保留最小距离的边即可 } System.out.println(dijkstra(g, n)); } /** * @param g 图的邻接矩阵表示 * @param n 图中点的个数 * **/ static int dijkstra(int[][] g, int n) { int[] distance = new int[n + 1]; boolean[] visited = new boolean[n + 1]; //状态变量 Arrays.fill(distance, INF); // 初始化距离为正无穷 distance[1] = 0; // 起点的距离为0 // 循环n次 for (int i = 0; i < n; i++) { // 先找出距离最小的点 int min = 0; for(int j = 1; j <= n; j++) { if (!visited[j] && distance[j] < distance[min]) { min = j; } } if (min == 0) break; // 所有点都遍历结束 // 找到了距离最小的点 visited[min] = true; // 这里是为了解决自环 // 更新距离, 枚举所有列 for(int j = 1; j <= n; j++) { // 当存在一个出边时, 更新其距离 if (g[min][j] != INF) distance[j] = Math.min(distance[j], distance[min] + g[min][j]); } } if (distance[n] == INF) return -1; else return distance[n]; } }
堆可以自己手写(用数组模拟),也可以使用现成的(C++的STL提供了priority_queue,Java的JDK中提供了PriorityQueue)
练习题:acwing - 850: Dijkstra求最短路 II
题解:手写堆(C++)
#include<iostream> #include<cstring> #include<algorithm> using namespace std; // 稀疏图, 用邻接表来存储, 并且选用堆优化的Dijkstra const int N = 2e5; const int INF = 0x3f3f3f3f; // 正无穷 int h[N], e[N], w[N], ne[N], idx; // 邻接表存储, -1表示空节点 int d[N]; // 距离 bool visited[N]; // 状态 int n, m; int hVal[N], hDis[N], hSize; // 数组模拟堆, hVal存节点编号, hDis存节点距离 int ph[N], hp[N]; // 记录堆中节点下标和图中节点编号的映射关系 // 交换2个下标, 下标是堆中的下标 void heap_swap(int a, int b) { swap(hp[a], hp[b]); swap(ph[hp[a]], ph[hp[b]]); swap(hVal[a], hVal[b]); swap(hDis[a], hDis[b]); } // 向上调整, 记得是根据距离hDis来调整 void up(int pos) { while(pos / 2 >= 1 && hDis[pos / 2] > hDis[pos]) { heap_swap(pos, pos / 2); pos /= 2; // 少写了这一行, 找了1小时! } } // 向下调整, 记得是根据距离hDis来调整 void down(int pos) { int min = pos; if(2 * pos <= hSize && hDis[2 * pos] < hDis[min]) min = 2 * pos; if(2 * pos + 1 <= hSize && hDis[2 * pos + 1] < hDis[min]) min = 2 * pos + 1; if(min != pos) { heap_swap(pos, min); down(min); } } // 获取并弹出堆顶节点 int pop() { if(hSize == 0) return 0; // 堆为空 int res = hVal[1]; // 节点编号 heap_swap(1, hSize); // 交换堆顶和堆尾 hSize--; // down(1); // 调整堆 return res; } // 插入一个节点到堆, x是节点编号, dis是该节点到起点的距离 void insert_to_heap(int x, int dis) { // 下标从1开始 hSize++; ph[x] = hSize; hp[hSize] = x; // 插入一个数到堆 hVal[hSize] = x; // 记录节点编号 hDis[hSize] = dis; // 记录节点距离 up(hSize); // 向上调整 } // 在x和y之间连一条边, 权重是z void add(int x, int y, int z) { // 记录该条边到邻接表 e[idx] = y; w[idx] = z; ne[idx] = h[x]; h[x] = idx++; } int dijkstra() { d[1] = 0; // 初始化, 起点(1号点)距离为0 insert_to_heap(1, 0); // 将起点插入堆 for(int i = 1; i <= n; i++) { // 每次确定一个节点 int t = pop(); // 获取当前距离最短的点, 节点编号为1~n if(t == 0) break; // 堆中没有元素, 表明节点已全部访问过, 提前结束 if(visited[t]) continue; // 该点已经在集合s中, 直接跳过 visited[t] = true; // 更新所有出边的点的距离 for(int j = h[t]; j != -1; j = ne[j]) { int u = e[j]; // 节点编号 int du = w[j]; // 边长 if(d[u] > d[t] + w[j]) { d[u] = d[t] + w[j]; insert_to_heap(u, d[u]); // 重复的点也可以直接插入, 没有关系 } } } if(d[n] == INF) return -1; else return d[n]; } int main() { memset(h, -1, sizeof h); // 初始化 memset(d, 0x3f, sizeof d); // 距离初始化为INF memset(hVal, 0, sizeof hVal); memset(hDis, 0, sizeof hDis); scanf("%d%d", &n, &m); while(m--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); } printf("%d", dijkstra()); return 0; }
题解:使用现成的堆(Java)
import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; /** * @Author yogurtzzz * @Date 2021/6/25 9:33 * * 堆优化版的 Dijkstra * 稀疏图, 用邻接链表来存 **/ public class Main { static class Pair { int first; int second; Pair(int first, int second) { this.first = first; this.second = second; } } static Scanner scanner = new Scanner(System.in); static int INF = 0x3f3f3f3f; static final int N = 200000; static int[] h; static int[] e = new int[N], w = new int[N], ne = new int[N];// 图的邻接表表示, 数组模拟链表 static int idx; // 用来分配链表节点 public static void main(String[] args) { int n = readInt(), m = readInt(); h = new int[n + 1]; Arrays.fill(h, -1); // 初始化, 全部邻接表都是-1, 表示空链表 while(m-- > 0) { int x = readInt(), y = readInt(), z = readInt(); add(x, y, z); } System.out.println(dijkstra(n)); } private static int dijkstra(int n) { int[] distance = new int[n + 1]; boolean[] visited = new boolean[n + 1]; Arrays.fill(distance, INF); distance[1] = 0; // 初始化起点距离 // 小根堆 PriorityQueue<Pair> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.first)); heap.offer(new Pair(0, 1)); // 插入起点到堆中, first是距离, second是节点编号 for(int i = 0; i < n; i++) { Pair p = heap.poll(); // 获取当前距离最小的节点 if (p == null) break; // 堆里没有元素了, 提前结束 int nodeNo = p.second, nodeDis = p.first; // 获取该节点的编号和距离 visited[nodeNo] = true; // 解决自环 for(int j = h[nodeNo]; j != -1; j = ne[j]) { // 从邻接表中获取该节点的所有出边, 依次更新 int nextNodeNo = e[j]; int nextNodeWeight = w[j]; if (distance[nextNodeNo] > nodeDis + nextNodeWeight) { // 更新 distance[nextNodeNo] = nodeDis + nextNodeWeight; // 插入到堆中 heap.offer(new Pair(distance[nextNodeNo], nextNodeNo)); } } } return distance[n] == INF ? -1 : distance[n]; } // 添加一条边 private static void add(int x, int y, int z) { e[idx] = y; w[idx] = z; ne[idx] = h[x]; h[x] = idx++; } private static int readInt() { return scanner.nextInt(); } }
算法思路
循环n次
每次循环,遍历图中所有的边。对每条边
(a, b, w)
,(指的是从a点到b点,权重是w的一条边)更新d[b] = min(d[b], d[a] + w)
(可以定义一个类,或者C++里面的结构体,存储a,b,w。表示存在一条边a点指向b点,权重为w)。则遍历所有边时,只要遍历全部的结构体数组即可
循环的次数的含义:假设循环了k次,则表示,从起点,经过不超过k条边,走到每个点的最短距离。
该算法能够保证,在循环n次后,对所有的边(a, b, w)
,都满足d[b] <= d[a] + w
。这个不等式被称为三角不等式。上面的更新操作称为松弛操作。
该算法适用于有负权边的情况。
注意:如果有负权回路的话,最短路就不一定存在了。(注意是不一定存在)。当这个负权回路处于1号点到n号点的路径上,则每沿负权回路走一圈,距离都会减少,则可以无限走下去,1到n的距离就变得无限小(负无穷),此时1号点到n号点的最短距离就不存在。而如果负权回路不在1号点到n号点的路径上,则1到n的最短距离仍然存在。
该算法可以求出来,图中是否存在负权回路。如果迭代到第n次,还会进行更新,则说明存在一条最短路,路径上有n条边,n条边则需要n + 1个点,而由于图中一共只有n个点,所以这n + 1个点中一定有2个点是同一个点,则说明这条路径上有环;有环,并且此次进行了更新,说明这个环的权重是负的(只有更新后总的距离变得更小,才会执行更新)。
但求解负权回路,通常用SPFA算法,而不用Bellman-Ford算法,因为前者的时间复杂度更低。
由于循环了n次,每次遍历所有边(m条边)。故Bellman-Ford算法的时间复杂度是O(n×m)。
练习题:acwing - 853: 有边数限制的最短路
#include<iostream> #include<cstring> using namespace std; const int N = 510, M = 10010; const int INF = 0x3f3f3f3f; struct Edge { int a, b, w; } edge[M]; // 直接用结构体来存储全部边 int n, m, k, d[N], tmp[N]; void bellman_ford() { memset(d, 0x3f, sizeof d); d[1] = 0; // 初始化 for(int i = 0; i < k; i++) { memcpy(tmp, d, sizeof d); // 需要备份 for(int j = 0; j < m; j++) { Edge e = edge[j]; int a = e.a, b = e.b, w = e.w; if(tmp[a] == INF) continue; if(d[b] > tmp[a] + w) { // 用上一次的d来进行计算, 以防出现串联的情况 // 更新 d[b] = tmp[a] + w; } } } if(d[n] == INF) printf("impossible"); else printf("%d", d[n]); } int main() { scanf("%d%d%d", &n, &m, &k); for(int i = 0; i < m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); edge[i] = {x, y, z}; } bellman_ford(); return 0; }
若要使用SPFA算法,一定要求图中不能有负权回路。只要图中没有负权回路,都可以用SPFA,这个算法的限制是比较小的。
SPFA其实是对Bellman-Ford的一种优化。
它优化的是这一步:d[b] = min(d[b], d[a] + w)
我们观察可以发现,只有当d[a]
变小了,才会在下一轮循环中更新d[b]
考虑用BFS来做优化。用一个队列queue,来存放距离变小的节点。
(和Dijkstra很像)
练习题:acwing - 851: spfa求最短路
#include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N = 1e5 + 10, INF = 0x3f3f3f3f; // 由于需要用到出边, 故用邻接表来存储图 int h[N], e[N], w[N], ne[N], idx; int d[N]; // 存储距离 int n, m; void add(int x, int y, int z) { e[idx] = y; w[idx] = z; ne[idx] = h[x]; h[x] = idx++; } void spef() { memset(d, 0x3f, sizeof d); // 初始化距离 d[1] = 0; queue<int> q; q.push(1); while(!q.empty()) { int t = q.front(); q.pop(); for(int i = h[t]; i != -1; i = ne[i]) { // 更新所有出边 int j = e[i]; if(d[j] > d[t] + w[i]) { d[j] = d[t] + w[i]; q.push(j); } } } if(d[n] == INF) printf("impossible"); else printf("%d", d[n]); } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); // 初始化邻接表, 全部为空链表 while(m--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); } spef(); return 0; }
SPFA的好处:能解决无负权边的问题,也能解决有负权边的问题,并且效率还比较高。但是当需要求在走不超过k条边的最短路问题上,就只能用Bellman-Ford算法了。
练习题:acwing - 852: spfa求负环
基本思路是,添加一个变量int ctn[N]
,来记录走到第i
个点所经过的边的长度即可,如果走到某个点的边的个数大于n,则说明存在负权回路
#include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N = 1e5 + 10, INF = 0x3f3f3f3f; // 由于需要用到出边, 用邻接表来存储图 int h[N], e[N], w[N], ne[N], idx; int d[N]; // 存储距离 int ctn[N]; bool visited[N]; int n, m; void add(int x, int y, int z) { e[idx] = y; w[idx] = z; ne[idx] = h[x]; h[x] = idx++; } void spef() { queue<int> q; for(int i = 1; i <= n; i++) { q.push(i); visited[i] = true; } memset(d, 0x3f, sizeof d); // 初始化距离 d[1] = 0; while(!q.empty()) { int t = q.front(); q.pop(); visited[t] = false; for(int i = h[t]; i != -1; i = ne[i]) { // 更新所有出边 int j = e[i]; if(d[j] > d[t] + w[i]) { d[j] = d[t] + w[i]; ctn[j] = ctn[t] + 1; if(ctn[j] >= n) { printf("Yes"); return; } if(!visited[j]) q.push(j); } } } printf("No"); } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); // 初始化邻接表, 全部为空链表 while(m--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); } spef(); return 0; }
求解多源汇最短路问题,也能处理边权为负数的情况,但是无法处理存在负权回路的情况。
使用邻接矩阵来存储图。初始使用d[i][j]
来存储这个图,存储所有的边
算法思路:三层循环
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
d[i,j] = min(d[i,j] , d[i,k] + d[k,j])
循环结束后,d[i][j]
存的就是点i
到j
的最短距离。
原理是基于动态规划(具体原理在后续的动态规划章节再做详解)。
其状态表示是:d(k, i, j)
,从点i
,只经过1 ~ k
这些中间点,到达点j
的最短距离
练习题:acwing - 854: Floyd求最短路
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 210, INF = 0x3f3f3f3f; int g[N][N]; // 邻接矩阵存储 int n, m, k; void floyd() { for(int p = 1; p <= n; p++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(g[i][p] != INF && g[p][j] != INF) g[i][j] = min(g[i][j], g[i][p] + g[p][j]); } } } } int main() { scanf("%d%d%d", &n, &m, &k); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i == j) g[i][j] = 0; else g[i][j] = INF; } } while(m--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); g[x][y] = min(g[x][y], z); // 处理重边 } floyd(); while(k--) { int x, y; scanf("%d%d", &x, &y); if(g[x][y] == INF) printf("impossible\n"); else printf("%d\n", g[x][y]); } return 0; }