最长路

最长路是与最短路相对应的概念，最短路是指路径长度最短的路径，最长路则是路径长度最长的路径。

最长路的求解方法主要有两种：SPFA算法和拓扑排序算法。拓扑排序算法的执行效率通常显著高于SPFA算法。需要说明的是，尽管SPFA算法存在容易被特殊数据构造卡时间的情况，但该算法在处理负边权问题上具有独特价值，建议学习者掌握该算法。

SPFA算法

SPFA算法能够处理包含负边权的图结构。由于负数的特性，数值越小其绝对值越大，因此可以将最长路问题转化为最短路问题求解。具体方法为：在存储边权时取其相反数，通过最短路算法求解后，再将结果取相反数即可得到最长路的数值。

拓扑排序算法

拓扑排序算法的应用存在一定限制，仅适用于有向无环图，无法直接处理无向图等结构。该算法需要结合动态规划（DP）思想实现，具体思路可通过代码实现进行理解。以下通过例题进行讲解：

题面：最长路

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

例题：

Status

Problem

最长路

最长路

SPFA算法

拓扑排序算法

SPFA求最长路示例代码

拓扑排序求最长路示例代码

例题：

On this page