CSP WIKI

非严格次短路

在理解最短路和最长路的概念后，次短路的概念可定义为：除最短路之外的最短路径（允许与最短路长度相等）。

本文仅介绍一种常用方法，A*算法可用于求解K短路问题，因复杂度较高暂不展开。次短路的求解依赖于最短路的结果，需首先计算出最短路。

次短路的长度必然大于或等于最短路长度。通过分析可知，次短路至少存在一条边不属于最短路径（可能与最短路径无交集）。基于此特性，求解次短路的思路为：记录最短路径中的边，依次删除最短路径中的每条边后重新计算最短路，通过比较所有结果得到次短路。以下通过例题具体说明：

例题：集合位置

该问题为次短路的典型模板题。解题步骤如下：

1、首先构建图结构（注意使用双精度浮点型存储边权及结果，并进行精度处理）

2、然后执行“计算最短路→记录路径→枚举删除路径边并重新计算最短路→处理结果”的流程。

需注意特殊情况处理：若存在多条最短路径，删除部分边后仍可能得到最短路；若起点与终点间仅有一条简单路径（即最短路），删除边后可能导致无法到达终点，此时次短路无解。

#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;
}

严格次短路

使用非严格次短路的算法求解此题时会出现错误，因该问题要求严格次短路（长度必须严格大于最短路）。

严格次短路的求解需确保结果严格大于最短路长度。

具体方法为：预处理双向最短路，使用d1数组存储起点到各点的最短路长度，d2数组存储各点到终点的最短路长度。通过枚举所有边，结合双向最短路数据计算严格次短路。

#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;
}

例题：

Status

Problem

单源次短路径

非严格次短路

严格次短路

例题：

On this page