基本原则
首先看题目n的数量级，当 n<1000 时，可以使用 [Floyd算法] 快速秒杀几乎所有题型
否则 若题目中所有边全为正权，则使用 [Dijkstra算法]
否则 当出现负权时，使用 [spfa算法]
注意一些隐蔽的最短路问题，比如题目会换一种问法。详见最短路的各种变形题。
一、正权单源最短路 —— Dijkstra算法
1. 定义
计算正权图上的单源最短路，即从单个源点出发到所有结点的最短路。包含无向图或有向图。
2. 解析
使用Dijkstra算法。时间复杂度O(mlgn)，一般够用。
3. 模板
struct node { // node结构是存放在优先队列中的结构
int u, d;
node(int u, int d) : u(u), d(d) {}
bool operator < (const node& rhs) const {
return d > rhs.d; // 由于默认为最大堆, 而我们希望最小的先出列
}
};
struct edge { //edge结构仅用于存图
int to, w;
edge(int to, int w) : to(to), w(w) {}
};
vector<edge> G[maxn];
int n, m, vis[maxn], d[maxn];
void Dij(int s) {
fill(d, d + n + 1, INF), d[s] = 0; // 初始化d数组
fill(vis, vis + n + 1, 0);
priority_queue<node> que;
que.push(node(s, 0));
while(!que.empty()) {
int u = que.top().u;
que.pop();
if(vis[u]) continue; // vis就写在这两行，是为了忽略掉松弛前的结点（因为并没有从队列中删除，只是压入了d更小的状态而已），
vis[u] = 1; // 因此放在这里进行判断，这是和bfs不同的
for(const edge& e : G[u]) {
if(d[e.to] > d[u] + e.w) { // 松弛操作
d[e.to] = d[u] + e.w;
que.push(node(e.to, d[e.to])); // 压入了松弛后的结点，然而并没有删除原结点，因此要依靠上面的vis
}
}
}
}
int main() {
......
Dij(1);
......
}注意Dijkstra的模板和bfs有点像，但是还是不一样的：
- 一个用优先队列，一个用普通队列
- 使用vis数组的原因不同
4. 例题
Poj 2397：https://blog.nowcoder.net/n/6b480880426c40aa85364d69565b621e
Poj 1847
Poj 1502
二、带负权的单源最短路 —— spfa算法
1. 定义
计算带负权的图上的单源最短路，由于可能存在负环，因此Dijkstra算法不可用。
2. 解析
这时可以使用spfa算法。最坏时间复杂度O(nm)。
带负权的最短路径问题，可以使用Bellman-Ford或它的优化版本，即spfa算法。spafa算法能解决带负权的单源最短路问题，同时判断是否存在负环。最坏时间复杂度为O(nm)。比Dijkstra慢，因此对于正权的单源最短路我们使用Dijkstra，而对于带负权的就只能使用spfa算法了。
spfa算法的原理：先从Bellman-Ford算法的原理开始，Bellman-Ford算法通过将每条边松弛n-1次来求出每个点的最终d[maxn]，即松弛到不能再松弛了。而如果第n次还存在边可以继续松弛，说明存在负环。而spfa通过让已经松弛得不能再松弛的边不再入队来实现减少冗余的松弛操作，用队列来存储每一轮迭代后还需要继续松弛的边，就是这样一个优化。
spfa的模板与Dijkstra有点像，需要注意区分。
3. 模板
struct edge { // 用于存图的edge结构
int to, w;
edge(int to, int w) : to(to), w(w) {}
};
vector<edge> G[maxn];
int n, inq[maxn], cnt[maxn], d[maxn];
bool spfa(int s) {
fill(d, d + n + 1, INF); d[s] = 0;
fill(inq, inq + n + 1, 0); // inq用于标记每个点是否在队列中
fill(cnt, cnt + n + 1, 0); // cnt用于统计每个点的入队次数
queue<int> que; // 只需要使用普通队列
que.push(s), inq[s] = 1, ++ cnt[s];
while(!que.empty()) {
int u = que.front(); que.pop();
inq[u] = 0; // 可以重复入队
for(const edge& e : G[u]) {
if(d[e.to] > d[u] + e.w) { // 松弛操作
d[e.to] = d[u] + e.w;
que.push(e.to), inq[e.to] = 1;
if(++ cnt[e.to] > n) return 1; // 入队超过n次说明有负环
}
}
}
return 0;
}
int main() {
......
spfa(1);
......
}- 要注意区分Dijkstra模板和spafa模板：
- Dijkstra使用优先队列，spfa使用普通队列
- Dijkstra使用vis数组排出重复点；spfa使用inq记录是否在队列中，用cnt记录入队次数，允许重复入队
- 若原图不连通，需要加一个点使得原图连通后再用spfa算法来判断负环，否则会漏判。
4. 例题
Poj 3259：https://blog.nowcoder.net/n/cea9e8a2dc5b4edea95df9a3f9a57119
Poj 3169
LightOJ 1074
三、多源最短路 —— Floyd算法
1. 定义
求任意两点之间的最短路。包含无向图或有向图，正权图、负权图。
2. 解析
使用Floyd算法。时间复杂度O(n^3)。对于多源最短路问题只能使用Floyd算法，对于单源最短路问题，若n比较小，也可以使用Floyd算法来快速解决。因为代码简单啊😀
3. 模板
const int INF = 1 << 29;
int n, d[maxn][maxn];
void init() {
for(int i = 1; i <= n; i ++) { // 初始化d
for(int j = 1; j <= n; j ++) d[i][j] = INF;
d[i][i] = 0;
}
}
void Floyd() {
for(int k = 1; k <= n; k ++) { // 枚举中间点
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= n; j ++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
int main() {
......
init();
Floyd();
......
}- 要注意Floyd中会有INF相加的情况，因此INF值不能太大，这里取的是1<<29.
4. 例题
Uva 567：https://blog.nowcoder.net/n/693ed45e3cad49b4b7e51e525bea3de7
四、差分约束问题与最短路的关系
1. 定义
即给出对n个数m组约束不等式，求其中某两个数的最值。
2. 解析
差分约束问题可以转化为最短路/最长路问题解决。
原理：以问最大值为例，问x-y<=多少时，肯定是通过若干B-A<=w的约束条件才可能获得，而B-A<=w这一不等式可以理解为d[B]<=d[A]+w，这正好符合与最短路问题中的松弛操作的条件（d[u]>d[v]+w）相反，也就是松弛操作会使得这一个个约束条件被满足，因此最短路问题的算法就可以得到满足所有约束条件的不等式的一组解。这样就可以得到d[x]与d[y]的差值了。
3. 模板
具体规则如下：
- 首先看问题，若问题问最大值则可以转化为最短路问题；问最小值则可以转化为最长路问题；
- 若为最短路问题，则将所有约束转化为B-A<=w的形式；最长路问题则转化为B-A>=w的形式；
- B-A<=w对应于d[B]<=d[A]+w，也就是从点A到B的有向路径权值为w；
然后就可以用Dijkstra、spfa或Floyd算法来秒杀了。 - 若存在负环，则表示无解；若d为INF，表示有无限个解。
4. 例题
Poj 3159：https://blog.nowcoder.net/n/4ab5d9ec4f3945829d259dc8c23dc5fa
五、几种常见的最短路变形题
1. 求最大边权的最小值 / 最小边权的最大值
做法
以求最大边权的最小值为例：- Floyd做法：
原松弛操作：d[i][j]= min(d[i][j], d[i][k] + d[k][j]);
变形后的松弛操作：d[i][j]= min(d[i][j] ,max( d[i][k] , d[k][j])); - Dijkstra/spfa算法：
原松弛操作 ： d[v]= min(d[v], d[u]+w);
变形后的松弛操作 ： d[v]= min(d[v] , max(d[u], w));
- Floyd做法：
例题
Poj 2253
Poj 1797
2. 求往返最短路的最大值 / 和
做法
- 数据量小的用Floyd算法秒杀；
- 否则通过对原图和反图（所有有向边反向）各做一次Dijkstra/spfa来解决。
例题
Poj 1511
Poj 3268
3. 确定排名
做法
用Floyd算法，dp[u][v]表示u打败了v：- 原松弛操作 ： d[i][j]= min(d[i][j], d[i][k] + d[k][j]);
- 变形后的松弛操作 ： d[i][j] = (d[i][k] && d[k][j]) ? 1 : 0;
例题
Poj 3660
[最短路变形] 参考博客：https://blog.csdn.net/JiangHxin/article/details/101999496
[差分约束] 参考博客：https://blog.csdn.net/whereisherofrom/article/details/78922648
京公网安备 11010502036488号