最短路 || 最长路 || 次短路
Poetic_Rain
2020-07-01 21:00:09
如题，这篇博客就讲一讲最短路以及其它 ~~乱七八糟~~ 的处理路径的问题
至于邻接表，邻接矩阵，有向边和无向边等基础概念之类的这里就不过多阐述了，不会的话建议先在其他dalao的博客或者书上面学习（请多谅解）
------------
# 最短路
首先讲最短路，因为最短路比较基础，而且在图论中也应用较多，在学习了最短路只会就可以继续往后面学习了，如果您已经学习过了，可以直接跳到后面的最长路和次短路中
最短路，在一个图中，求一个地方到另一个地方的最短路径。联系到我们之前学过的**广度优先搜索**中，也可以处理类似的问题，所以我们先想一想广度优先搜索的一些思想——**队列**。所以在接下来的最短路算法中，或多或少的会涉及到队列
### 单源最短路径
单源最短路径，就是指在一个图中，给你一个起点（起点固定），然后终点不是固定的，求起点到任意终点的最短路径。这里会涉及到3种算法，以下用$dis[]$表示起点到任意终点的最短距离
#### 1. Bellman-Ford算法
时间复杂度：$O(nm)$
给定一个图，对于图中的某一条边$(x,y,z)$，$x$和$y$表示两个端点，$z$表示连接两条边的边权，如果有所有边都满足$dis[y]≤dis[x]+z$，则$dis[]$数组的值就是要求的最短路径
这个算法的流程就是基于以上的式子进行操作的：
```
1.扫描所有的边，如果有 d[y]>d[x]+z ，则 d[y]=d[x]+z （这也被叫做松弛操作）
2.重复以上的操作，知道所有边无法进行松弛操作
```
还是比较好理解的，这里就不挂上代码了，因为讲这个算法的目的是为了下一个算法作铺垫
#### 2. SPFA算法
时间复杂度：$O(km)$ （$k$为一个较小的常数）
SPFA算法其实就是用队列优化过后的Ford的算法，~~所以没事别用Ford算法~~ ，所以它的算法实现和Ford算法其实是有相似之处的：
```
1.建立队列，起初队列中的节点只有起点
2.取出队头的点 x ，然后扫描 x 的所有出边（x,y,z）进行松弛操作，如果 y 不在队列中，将 y 入队
3.重复以上操作，直到队列为空
```
------分割线，下面是代码------
```
int head[MAXN],tot;
struct edge{
int net,to,w;
}e[MAXN];
void add(int x,int y,int z){
e[++tot].net=head[x];
e[tot].to=y;
e[tot].w=z;
head[x]=tot;
}
//以上是链式前向星的建边
bool v[MAXN]; //是否入队
int dis[MAXN],vis[MAXN]; //dis为最短距离，vis为入队次数，如果入队次数太多，说明该图中有环
queue<int>q; //队列
bool spfa(int s){
for(register int i=1;i<=n;i++) dis[i]=INF,v[i]=false; //初始化
d[s]=0,v[s]=true;
vis[s]++;
q.push(s);
while(!q.empty()){
int x=q.front();
q.pop(); //取出队头
v[x]=false;
if(vis[x]>n) return false; //超过了n次，就说明有环
for(register int i=head[x];i;i=e[i].net){ //扫描x的出边
int y=e[i].to,z=e[i].w;
if(d[y]>d[x]+z){ //松弛操作
d[y]=d[x]+z;
if(v[y]==false){ //是否入队
v[y]=true;
vis[y]++;
q.push(y);
}
}
}
}
return true;
}
```
相信大家都听说过流传于OI界的一句话“关于SPFA，它死了”，是因为有的出题人故意出数据卡SPFA，所以SPFA的时间复杂度会退化为Ford，所以在下面又会介绍一种超级香的算法
#### 3. Dijkstra算法
~~SPFA已死，Dijkstra当立！！！~~
这里先讲DIjkstra的算法流程：
```
1.初始化dis[]为极大值，起点为0
2.找出一个没有被标记过的且dis[]值最小的节点x，然后标记点x
3.扫描x的出边，进行松弛操作
4.重复以上步骤，直到所有点都被标记
```
这里不难看出Dijkstra是基于贪心思想的一种最短路算法，我们通过一个已经确定了的最短路$dis[x]$，然后不断找到全局最小值进行标记和扩展，最终实现算法，其实对于以上的步骤，也可以进行一个堆优化（优先队列优化），所以下面我会给出两个程序段
未优化 时间复杂度：$O(n^2)$
```
int dis[MAXN];
bool v[MAXN];
void Dijkstra(int s){
for(register int i=1;i<=n;i++) dis[i]=INF,v[i]=false;
d[s]=0; //初始化
for(register int i=1;i<n;i++){
int x=0;
for(register int j=1;j<=n;j++){
if(v[j]==false&&(x==0||d[j]<d[x])) x=j;
} //找到最小的x
v[x]=true;
for(register int y=1;y<=n;y++){
d[y]=min(d[y],d[x]+a[x][y]);
} //松弛操作
}
}
···
···
for(register int i=1;i<=n;i++){
for(register int j=1;j<=n;j++){
a[i][j]=INF;
}
a[i][i]=0;
}
for(register int i=1;i<=m;i++){
int x,y,z;
a[x][y]=min(a[x][y],z); //取min是为了判断重边
} //建立邻接矩阵
```
堆优化 时间复杂度：$O(m log n)$
```
int head[MAXN],tot;
struct edge{
int net,to,w;
}e[MAXN];
void add(int x,int y,int z){
e[++tot].net=head[x];
e[tot].to=y;
e[tot].w=z;
head[x]=tot;
} //邻接表建边
int d[MAXN];
bool v[MAXN];
priority_queue<pair<int,int> >q;
//这里是建大根堆，利用相反数实现小根堆
//first为距离，second为编号
//按first从小到大排序
//或者你自己手写重载运算符
void Dijkstra(int s){
for(register int i=1;i<=n;i++) d[i]=INF,v[i]=false;
d[s]=0;
q.push(make_pair(0,s));
while(!q.empty()){
int x=q.top().second;
q.pop();
if(v[x]==true) continue;
v[x]=true;
for(register int i=head[x];i;i=e[i].net){
int y=e[i].to,z=e[i].w;
if(d[y]>d[x]+z){
d[y]=d[x]+z;
q.push(make_pair(-d[y],y));
//非常灵魂的取相反数
}
}
}
}
```
关于Dijkstra，它是真的很香，因为确实跑得很快，对于单源最短路的算法就介绍到这里了，但是对于这些算法的各自特点，我会留到最后来讲
### 多源最短路径
目前涉及到的还只有FLoyd算法，当然还有一个Johnson的全源最短路算法，因为用的不多，这里就不过多介绍
#### Floyd算法
时间复杂度：$O(n^3)$
对于Floyd的实现，其实非常的简单，它有一点像动态规划的方式，通过枚举所有中间点进行松弛操作，大概就是在直接路径和间接路径中取一个最小的，这里就直接挂上代码了
```
for(register int i=1;i<=n;i++){
for(register int j=1;j<=n;j++){
d[i][j]=INF;
}
d[i][i]=0;
}//邻接矩阵存储,d[i][j]表示i到j的距离
for(register int k=1;k<=n;k++){ //第一层枚举中间点
for(register int i=1;i<=n;i++){ //第二层枚举起点
for(register int j=1;j<=n;j++){ //第三层枚举终点
if(i!=j&&j!=k) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
//动态转移方程，在间接路径和直接路径中取最小值
}
}
}
```
### 总结
以上就是对于最短路的算法介绍，这里会对各种算法进行对比和总结，然后给出一些我个人认为好一点的例题
首先是Ford算法，不用说，能不用就别用，因为SPFA算法在大部分时候都比Ford算法优越，最多就和Ford算法一样
然后说SPFA，SPFA其实可以处理负边权和负环的情况，这是它的特点，而SPFA在不被卡的情况下其实是比Dijkstra更加快的（但是SPFA基本上都会被卡的死死的）
过了就是DIjkstra，这个算法其实算是可以优先选择，但是遇到环和负边权的情况，它是完全不能处理的，这个时候就要回去考虑SPFA了
对于FLoyd，如果不是多源最短路就可以不考虑，因为二维数组的空间不会太大，并且$n^3$的时间复杂度估计没人会接受吧，但是Floyd（Floyd的变种）有一些其它的应用，这里不会涉及
先上两道通用的**模板题**：
第二道其实完全可以不考虑，但是还是要放一下，这样你们才能自己亲身感受一下上面各类算法的区别，建议大家各种算法都试一试（SPFA真的死得特别惨）
[P4779 【模板】单源最短路径（标准版）](https://www.luogu.com.cn/problem/P4779)
[P3371 【模板】单源最短路径（弱化版）](https://www.luogu.com.cn/problem/P3371)
然后就是其它的一些单独的算法了：
**Dijkstra**：
[P1396 营救](https://www.luogu.com.cn/problem/P1396)
[P5651 基础最短路练习题](https://www.luogu.com.cn/problem/P5651)
[P1529 [USACO2.4]回家 Bessie Come Home](https://www.luogu.com.cn/problem/P1529#submit)
[P1629 邮递员送信](https://www.luogu.com.cn/problem/P1629)
这几道题中，邮递员送信会涉及到一点反向图的知识，可以去看我的另一篇博客（~~啊。无耻~~）。回家那道题难在一些字符串的处理上。剩下两道题就比较模板了，考验大家对算法的本质的一些认识
**SPFA**：
[P1938 [USACO09NOV]Job Hunt S](https://www.luogu.com.cn/problem/P1938)
我是真的没有找到几道必须用SPFA做的题，所以大家见谅啊，但是所有能用Dijkstra的都可以用SPFA，但是一般会被卡。。。这道题难在处理点权和边权的关系上面
**Floyd**：
[P1364 医院设置](https://www.luogu.com.cn/problem/P1364)
[P1119 灾后重建](https://www.luogu.com.cn/problem/P1119)
[P1522 [USACO2.4]牛的旅行 Cow Tours](https://www.luogu.com.cn/problem/P1522)
如果你能自己A掉上面的题，证明你对Floyd的理解已经很深很透彻了，所以在思维难度上是比较高的
**最短路的综合练习**：
[P1608 路径统计](https://www.luogu.com.cn/problem/P1608)
[P1144 最短路计数](https://www.luogu.com.cn/problem/P1144)
[P1186 玛丽卡](https://www.luogu.com.cn/problem/P1186)
这三道题就是用来告诉你如何记录最短路的路径的，为之后的次短路的算法作一下铺垫吧，顺便加深理解。这里就不放代码了，如果不会的话可以去看看我的博客或者其他dalao的题解
------------
# 最长路
最长路，顾名思义嘛，最短路就是道路最短，那就最长路就是道路最长了咯
最长路的求法也有两种，一种是SPFA，一种是拓扑排序，拓扑排序跑得比SPFA快很多，这里也要说一下，虽然SPFA容易被卡，但是希望那些认为SPFA没用的人也去学一学，这是很有必要的（~~尽管我知道用SPFA的人很多~~）
**首先讲SPFA**，我们知道SPFA算法可以处理负边权的问题，如果你上过小学，那么你肯定知道，一个负数越小，那它的绝对值肯定更大。这样我们就可以把最长路问题转换为最短路问题了
相比读者肯定已经想到了，在存边的时候，我们只需要把边权取一个相反数，然后正常地求最短路，在最后的答案中取一个相反数就可以了，是不是很简单？
然后是拓扑排序，不知道或是不了解拓扑排序的可以看一下这篇博客（~~继续无耻~~），[同桌的拓扑排序](https://www.cnblogs.com/Eleven-Qian-Shan/p/13215825.html)
了解拓扑排序之后，我们其实可以知道使用拓扑排序的话是有限制的，它只能处理有向无环图，无向图这些都不能处理，但是还是要去学。使用拓扑排序的话，需要用到一些DP的思想，这个地方不太好讲解思路，直接在代码里面看实现方法
这里就直接用一个例题来讲解了
[P1807 最长路](https://www.luogu.com.cn/problem/P1807)
### SPFA
```
#include <bits/stdc++.h>
using namespace std;
int n,m,u,v,w,tot;
int dis[510010],vis[510010],head[510010];
struct node {
int to,net,val;
} e[510010];
inline void add(int u,int v,int w) {
e[++tot].to=v;
e[tot].net=head[u];
e[tot].val=w;
head[u]=tot;
}
//链式前向星建边
inline void spfa() {
queue<int> q;
for(register int i=1;i<=n;i++) dis[i]=20050206;
dis[1]=0;
vis[1]=1;
q.push(1);
while(!q.empty()) {
int x=q.front();
q.pop();
vis[x]=0;
for(register int i=head[x];i;i=e[i].net) {
int v=e[i].to;
if(dis[v]>dis[x]+e[i].val) {
dis[v]=dis[x]+e[i].val;
if(!vis[v]) {
vis[v]=1;
q.push(v);
}
}
}
}
}//正常跑最短路
int main() {
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++) {
scanf("%d%d%d",&u,&v,&w);
add(u,v,-w);//非常灵魂地存一个相反数
}
spfa();
if(dis[n]==20050206) puts("-1"); //到不了就-1
else printf("%d",-dis[n]);//记得存回来
return 0;
}
```
------------
### 拓扑排序
```
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2*5*1e4;
int n,m;
struct edge{
int net,to,w;
}e[MAXN];
int head[MAXN],tot;
void add(int x,int y,int z){
e[++tot].net=head[x];
e[tot].to=y;
e[tot].w=z;
head[x]=tot;
}
//链式前向星建边
bool v[MAXN];
//用来标记是否可以从1走到这个点
//因为是1到n，所以如果不能从1开始走
//说明不满足条件，没有这条最长路
int ru[MAXN];
int ans[MAXN];
queue<int>q;
void toop(){
for(register int i=1;i<=n;i++){
if(ru[i]==0) q.push(i);
}//入度为0的进队
while(!q.empty()){
int x=q.front();
q.pop();//出队
for(register int i=head[x];i;i=e[i].net){
int y=e[i].to,z=e[i].w;
ru[y]--;//入度--
if(v[x]==true){
ans[y]=max(ans[y],ans[x]+z);
v[y]=true;
}//如果这个节点能从1走到，说明它的边可以走
//更新最长路
if(ru[y]==0) q.push(y);//进队
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
ru[v]++;
}//建边，入度++
v[1]=true;//1肯定自己能走
ans[n]=-1;//初始值为-1，方便输出
toop();//拓扑排序求最长路
cout<<ans[n];
return 0;
}
```
**最长路的其他题**：
[P1113 杂务](https://www.luogu.com.cn/problem/P1113)
[P6145 [USACO20FEB]Timeline G](https://www.luogu.com.cn/problem/P6145)
------------
# 非严格次短路
有了最短路和最长路，那么肯定就有次短路，还是很好理解的，就是第二短路（除了最短路的最短路）
这里的话，我就只介绍一种方法了，还有一个**A star算法** 这貌似都可以用来做K短路了，我想都不敢想（好吧，单纯就是我不会，如果我学会了我会回来更的）
简明扼要的来说，我们求次短路，肯定和最短路脱不了干系，所以怎么说要先把最短路跑出来，这样才能有一个拿来比较的东西
次短路，它肯定比最短路要长（废话），考虑一种非常极端的情况，次短路肯定不会是最短路（废话）,**那么次短路肯定至少有一条边不在最短路上**，明白这个很重要，当然它也可能是完全没有交集的两条边
了解之后，我们来想想到底怎么实现这个次短路。由上面的推断，我们肯定需要去记录最短路的路径和经过的节点，如果你无法理解这个东西，可以去上面找一找**玛丽卡和最短路计数两题**
我们可以尝试把最短路上的任意一条边删掉，然后重新跑最短路，这样就可以保证了我之后跑的所有最短路都比第一次的最短路要长，然后通过比较就可以求出次短路了，我们通过一道例题来具体理解一下
[P1491 集合位置](https://www.luogu.com.cn/problem/P1491)
这道题还是比较模板，其它次短路的题我并没有接触过多少，所以还是读者自己去领悟和多刷题（见谅）
拿到这道题后，肯定先把建边这些不那么重要的东西先处理掉，记得用double和一些精度处理，所有的边和存储答案都用double。然后按上面讲的思路实现一遍
**跑最短路 -> 记录路径 -> 枚举删边，再跑最短路 -> 处理答案**
但其实题目中还告诉了一些条件，就是关于一些无解的判断
这其实是很好理解的，如果存在多条最短路径，那我在枚举删除第一条最短路上的边的时候，是完全不影响其它最短路的，那么我们求出来的还是一条最短路，过掉
如果不存在第二短路径，说明起点和终点之间只存在一条简单路径，而这条路径就是最短路，如果删去边之后就无法到达终点了，特判一下就ok
那么思路就这么讲完了，我们直接用代码来加深理解一下
```
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7+50;
const double INF=200500305;
int n,m;
int x[MAXN],y[MAXN];
struct node{
int net,to,from;
double w;
}e[MAXN];
int head[MAXN],tot;
void add(int u,int v,double w){
e[++tot].net=head[u];
e[tot].to=v;
e[tot].from=u;
//这里的from和to表示这一条边的两个端点
//在后面的程序中用来比较求次短路
e[tot].w=w;
head[u]=tot;
}
//链式前向星建边
double d[MAXN];
int bian[MAXN]; //记录最短路
bool v[MAXN];
inline bool ok(int i,int j){
if(min(e[i].to,e[i].from)==min(e[j].to,e[j].from)&&max(e[i].to,e[i].from)==max(e[j].to,e[j].from))return 0;
return 1;
}//这一坨长长的东西用来判断是不是我这次要删掉的边
void dij(int s,int p){ //p用来表示删除哪一条边
priority_queue<pair<double,int> >q;
for(register int i=1;i<=n;i++) d[i]=INF,v[i]=false;
d[s]=0; //初始化
q.push(make_pair(0,s));
while(!q.empty()){
int x=q.top().second;
q.pop();
if(v[x]==true) continue;
v[x]=true;
for(register int i=head[x];i;i=e[i].net)
if(p==-1||ok(i,p)){ //如果是第一次跑最短路就记录路径，如果是该边被删去就不跑
int y=e[i].to;
double z=e[i].w;
if(d[y]>d[x]+z){
d[y]=d[x]+z;
if(p==-1)bian[y]=i; //第一次跑最短路记录路径
q.push(make_pair(-d[y],y));
}
}
}
}
double Min(double x,double y){
if(x<=y) return x;
return y;
} //c++自带的min不支持double类型的比较
int main(){
scanf("%d%d",&n,&m);
for(register int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for(register int i=1;i<=m;i++){
int u,v;
double w;
scanf("%d%d",&u,&v);
w=(double)sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]));
add(u,v,w);
add(v,u,w);
}//建双向变
dij(1,-1); //第一次跑最短路不删边
int t=n; //用t来代替n，遍历最短路的边
double ans=INF;
while(t!=1){
int i=bian[t];
dij(1,i);
ans=min(ans,d[n]); //取一个更小的答案表示次短路
t=e[bian[t]].from; //遍历最短路的路径
}
printf("%.2lf",ans); //输出答案
return 0;
}
```
感谢一下ZJY，同桌和RHL三位大佬提供的一些帮助啊
这篇博客就写到这里了，如果我误人子弟了，可以在评论区指出错误或者在QQ上告诉我，我会尽早改正，这么长的文章，谢谢阅读
------------
死不要脸的更新一下，果然误人子弟了（我错了大哥们）
以上介绍的次短路算法，其实是非严格的次短路算法，它的次短路和最短路可能相等（顺便吐槽一下，严格次小生成树跟个鬼一样。。），所以这里我会再讲一下如何求严格次短路
# 严格次短路
当你拿上面非严格次短路的程序和思想做[这一道题](https://www.luogu.com.cn/problem/P2865)的时候，会发现自己WA了一些或者一个点，因为这道题目说了，求严格次短路，而上面那一道题是允许相等的
那么如何求严格次短路呢？
首先严格次短路肯定比最短路要大，那么第一次还是需要跑一下最短路并记录这一个值
在上面求非严格次短路时，我们选择记录最短路中的路径，并枚举删除最短路中的每一条边。如果有一条边和删除的边权相同，并且可以到达终点，就会导致次短路和最短路相等
所以我们要跳出整个最短路，枚举所有边，这个时候可以我们可以预处理两条最短路，因为是双向边，我们用一个$d1$数组表示$1$到其他点的最短路，$d2$数组表示其他点到$n$的最短路，那么整个程序就写出来了
```
#include<bits/stdc++.h>
#define M 1000051
#define N 5005
using namespace std;
int n,m;
struct node{
int net,to,z;
}e[M];
int head[N],tot;
queue<int>q;
int d1[N],d2[N]; //同上
bool v[N];
void add(int x,int y,int z){
e[++tot].net=head[x];
e[tot].to=y;
e[tot].z=z;
head[x]=tot;
}
void spfas(int s){
for(register int i=1;i<=n;i++){
d1[i]=20040915,v[i]=false;
}
d1[s]=0;
v[s]=true;
q.push(s);
while(!q.empty()){
int x=q.front();
q.pop();
v[x]=false;
for(register int i=head[x];i;i=e[i].net){
int y=e[i].to,z=e[i].z;
if(d1[y]>d1[x]+z){
d1[y]=d1[x]+z;
if(v[y]==false){
v[y]=true;
q.push(y);
}
}
}
}
}
void spfae(int s){
for(register int i=1;i<=n;i++){
d2[i]=20040915,v[i]=false;
}
d2[s]=0;
v[s]=true;
q.push(s);
while(!q.empty()){
int x=q.front();
q.pop();
v[x]=false;
for(register int i=head[x];i;i=e[i].net){
int y=e[i].to,z=e[i].z;
if(d2[y]>d2[x]+z){
d2[y]=d2[x]+z;
if(v[y]==false){
v[y]=true;
q.push(y);
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
spfas(1); //预处理d1
spfae(n); //预处理d2
int minn=d1[n],now=20040915;
//记录最短路，并将次短路改为极大值
for(register int i=1;i<=n;i++){
for(register int j=head[i];j;j=e[j].net){ //枚举每一个点的出边
if(d1[i]+d2[e[j].to]+e[j].z>minn) now=min(now,d1[i]+d2[e[j].to]+e[j].z);
//如果比最短路大，那么更新次短路
}
}
cout<<now;
return 0;
}
```
应该不会更新了吧。。。说不定突然检查出来哪里有锅，先就这样了