文章目录
搜索与图论（二）
这一节讲的是最短路。
常见的最短路问题，一般分为两大类：
- 单源最短路
- 多源汇最短路
在最短路问题中，源点也就是起点，汇点也就是终点。
单源最短路
单源最短路，指的是求一个点，到其他所有点的最短距离。（起点是固定的，单一的）
根据是否存在权重为负数的边，又分为两种情况
-
所有边的权重都是正数
通常有两种算法
-
朴素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。
算法思路
朴素Dijkstra
假设图中一共有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];
}
}
堆优化版Dijkstra
堆可以自己手写（用数组模拟），也可以使用现成的（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();
}
}
Bellman-Ford
算法思路
循环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)。
#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，这个算法的限制是比较小的。
SPFA其实是对Bellman-Ford的一种优化。
它优化的是这一步：d[b] = min(d[b], d[a] + w)
我们观察可以发现，只有当d[a]变小了，才会在下一轮循环中更新d[b]
考虑用BFS来做优化。用一个队列queue，来存放距离变小的节点。
（和Dijkstra很像）
#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算法了。
基本思路是，添加一个变量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;
}
Floyd
求解多源汇最短路问题，也能处理边权为负数的情况，但是无法处理存在负权回路的情况。
使用邻接矩阵来存储图。初始使用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的最短距离
#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;
}