很多朋友对于高效单源最短路径求解方法解析和不太懂，今天就由小编来为大家分享，希望可以帮助到大家，下面一起来看看吧！
判断是否存在负循环：
如果一个点进入队列超过N次，则存在负循环。
算法伪代码：程序最短路径更快算法(G, s)
1 对于V(G) 中的每个顶点v s
2d(v) :=无穷大
3d(s) :=0
4 个报价进入Q
5 当Q 不为空时
6 u :=轮询Q
E(G) 中的每条边(u, v) 为7
8 如果d(u) + w(u, v) d(v) 那么
9 d(v) :=d(u) + w(u, v)
10 如果v 不在Q 中，则
11 提供v 进入QP3371 [模板] 单源最短路径
问题含义：
求从起点到每个点的最短路径
#include#include#include#includeusing 命名空间std;
常量整数MAXN=10010;
常量int MAXE=500010；
常量int INF=0x7fffffff;
结构节点
{
int 到，下一个，val；
};
节点边[MAXE]；
int cnt,头[MAXN];
int dis[MAXN],inque[MAXN];//判断是否在队列中
无效addEdge（int u，int v，int val）
{
边缘[cnt].to=v;边缘[cnt].val=val;
边缘[cnt].next=head[u];head[u]=cnt++;
}
无效spfa_bfs(int st)
{
memset(inque,0,sizeof(inque));
dis[st]=0；
排队；
que.push(st);
int u,v,i；
while(!que.empty())
{
u=que.front();que.pop();
inque[u]=0；
for(i=head[u];i!=-1;i=edge[i].next)
{
v=边[i].to；
if(dis[v]dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inque[v])
{
que.push(v);
inque[v]=1；
}
}
}
}
}
int main()
{
int n，m，st，u，v，val；
scanf("%d%d%d",n,m,st);
填充（dis+1，dis+1+n，INF）；
memset(头，-1,sizeof(头));
cnt=0；
for(int i=0;i虫洞
问题含义：
如果图形是连通的，判断负循环
解决方案：
选择spfa 的任意起点
#include#include#include#includeusing 命名空间std;
常量整数MAXN=10010;
常量int MAXE=500010；
常量int INF=0x3f3f3f3f;
结构节点
{
int 到，下一个，val；
};
节点边[MAXE]；
int cnt,头[MAXN];
int dis[MAXN],inque[MAXN];
int queNum[MAXN];//进入队列的条目数
无效addEdge（int u，int v，int val）
{
边缘[cnt].to=v;边缘[cnt].val=val;
边缘[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_bfs(int st,int n)
{
memset(inque,0,sizeof(inque));
memset(dis,INF,sizeof(dis));
memset(queNum,0,sizeof(queNum));
dis[st]=0；
排队；
que.push(st);
queNum[st]++；
int u,v,i；
while(!que.empty())
{
u=que.front();que.pop();
inque[u]=0；
for(i=head[u];i!=-1;i=edge[i].next)
{
v=边[i].to；
if(dis[v]dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inque[v])
{
que.push(v);
queNum[v]++；
if(queNum[v]n) return true;//存在负循环
inque[v]=1；
}
}
}
}
返回假；
}
int main()
{
int n、m、k、u、v、val、t；
scanf("%d",t);
同时（t--）
{
scanf("%d%d%d",n,m,k);
memset(头，-1,sizeof(头));
cnt=0；
for(int i=0;i其实spfa可以写成DFS的形式，只不过队列换成了栈！同时，用bfs形式的spfa来判断负环会很慢，因为对于有负环的情况我们必须在某个点入队n次后才能判断出来，如果n很大，那会非常耗时，而用DFS可以改善，因为DFS不会重复将一个点入栈，而是将下一个点入栈看看识别负循环的方法：
1、spfa中记录当前节点是否同时在栈中。 2、如果某个节点可以被当前节点松弛，并且该节点仍在栈中，则说明松弛路径中存在环路。出口。否则，以该节点为当前点进行深度搜索spfa操作但是，如果明确知道图中没有负环，只是求最短路径，还是要用BFS的spfa,DFS栈太深跑得比较慢!下面是spfa_dfs寻找最短路径的代码（其实负环已经可以确定）
畅通交通工程持续推进
问题含义：
给定起点和终点，找出最短路径
#include#include#includeusing 命名空间std;
常量整数MAXN=10010;
常量int MAXE=500010；
常量int INF=0x7fffffff;
结构节点
{
int 到，下一个，val；
};
节点边[MAXE]；
int cnt,头[MAXN];
int dis[MAXN],instack[MAXN];//判断是否在栈上
无效addEdge（int u，int v，int val）
{
边缘[cnt].to=v;边缘[cnt].val=val;
边缘[cnt].next=head[u];head[u]=cnt++;
}
布尔spfa_dfs(int u)
{
堆栈[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!instack[v])
{
if(spfa_dfs(v)) return true;//存在负循环
}
else return true;//存在负循环
}
}
堆栈[u]=0;
返回假；
}
int main()
{
int n，m，st，ed，u，v，val；
while(scanf("%d%d",n,m)!=EOF)
{
memset(头，-1,sizeof(头));
cnt=0；
for(int i=0;i虫洞
问题含义：
如果图形是连通的，判断负循环
解决方案：
选择spfa 的任意起点
#include#include#includeusing 命名空间std;
常量整数MAXN=10010;
常量int MAXE=500010；
常量int INF=0x3f3f3f3f;
结构节点
{
int 到，下一个，val；
};
节点边[MAXE]；
int cnt,头[MAXN];
int dis[MAXN],inStack[MAXN];//判断是否在栈中
无效addEdge（int u，int v，int val）
{
边缘[cnt].to=v;边缘[cnt].val=val;
边缘[cnt].next=head[u];head[u]=cnt++;
}
布尔spfa_dfs(int u)
{
inStack[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inStack[v])
{
if(spfa_dfs(v)) return true;//存在负循环
}
else return true;//存在负循环
}
}
inStack[u]=0;
返回假；
}
int main()
{
int n、m、k、u、v、val、t；
scanf("%d",t);
同时（t--）
{
scanf("%d%d%d",n,m,k);
memset(头，-1,sizeof(头));
cnt=0；
for(int i=0;i其实，如果只是判断负环，而不要求求最短路径，dfs的spfa还有一个优化的地方!首先，如果有负循环，那么一定有负边沿，如果我们一开始就从负边沿开始spfa_dfs，肯定会很快找到这个负循环找到负循环就退出，这样会快很多！
那么，你首先如何发现消极的一面呢？
我们先看spfa_dfs。现在我们要第一次扩展dfs。为了使第一次选择负边沿，假设我们将dis数组初始化为0。展开时，dis[u]=0，dis[v]=0，使dis[v]dis[u]+edge [i].val，那么边一定是负的，然后将负边扩展。
也就是说，dis数组初始化为0。这样处理后，第一次拓展只会拓展到与起点相连边权为负的边。当然，判断负环+求最短路径时不能这样初始化dis数组，因为可能存在权重为负且没有负环的路径，所以这样的最短路径是合理的，所以最好诚实地做。 dis 数组初始化为。
P3385 [模板] 负环路
问题含义：
给定一个图，判断是否存在负循环。请注意，图形不一定是连接的，因此来自单个源的最短负环路必须经过多个不同的起点。 （spfa_bfs会超时，spfa_dfs的dis数组如果不初始化为0也会超时）
#include#include#includeusing 命名空间std;
常量int MAXN=200010;
常量int MAXE=200010*2;
常量int INF=0x3f3f3f3f;
结构节点
{
int 到，下一个，val；
};
节点边[MAXE]；
int cnt,头[MAXN];
int dis[MAXN],inStack[MAXN];//判断是否在栈中
无效addEdge（int u，int v，int val）
{
边缘[cnt].to=v;边缘[cnt].val=val;
边缘[cnt].next=head[u];head[u]=cnt++;
}
布尔spfa_dfs(int u)
{
inStack[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inStack[v])
{
if(spfa_dfs(v)) return true;//存在负循环
}
else return true;//存在负循环
}
}
inStack[u]=0;
返回假；
}
int main()
{
int n，m，u，v，val，t；
scanf("%d",t);
同时（t--）
{
scanf("%d%d",n,m);
memset(头，-1,sizeof(头));
cnt=0；
for(int i=0;i=0) addEdge(v,u,val);
}
memset(inStack,0,sizeof(inStack));
memset(dis,0,sizeof(dis));
布尔标志=假；
for(int i=1;i=n;i++)
{
如果（spfa_dfs（i））
{
标志=真；
休息；
}
}
if(flag) printf("YE5n");
否则printf("N0n");
}
}此外，让我们使用全局变量标志给出另一个dfs。其实和上面是一样的。
#include#include#includeusing 命名空间std;
常量int MAXN=200010;
常量int MAXE=200010*2;
常量int INF=0x3f3f3f3f;
结构节点
{
int 到，下一个，val；
};
节点边[MAXE]；
int cnt,头[MAXN];
int dis[MAXN],inStack[MAXN];//判断是否在栈中
无效addEdge（int u，int v，int val）
{
边缘[cnt].to=v;边缘[cnt].val=val;
边缘[cnt].next=head[u];head[u]=cnt++;
}
布尔标志；
无效spfa_dfs(int u)
{
inStack[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inStack[v])
{
spfa_dfs(v);
if(flag) return;//存在负循环
}
别的
{
标志=真；
return;//存在负循环
}
}
}
inStack[u]=0;
}
int main()
{
int n，m，u，v，val，t；
scanf("%d",t);
同时（t--）
{
scanf("%d%d",n,m);
memset(头，-1,sizeof(头));
cnt=0；
for(int i=0;i=0) addEdge(v,u,val);
}
memset(inStack,0,sizeof(inStack));
memset(dis,0,sizeof(dis));
标志=假；
for(int i=1;i=n;i++)
{
spfa_dfs(i);
如果（标志）中断；
}
if(flag) printf("YE5n");
否则printf("N0n");
}
好了，本文到此结束，如果可以帮助到大家，还望关注本站哦！
【高效单源最短路径求解方法解析】相关文章：
2.米颠拜石
3.王羲之临池学书
8.郑板桥轶事十则
用户评论
这个算法真是太牛了！
有17位网友表示赞同！
听起来像个解迷题的技能吧！
有14位网友表示赞同！
原来还有专门解决路径长度问题的算法啊～
有20位网友表示赞同！
我要去看一下这单源最短路到底是如何工作的！
有17位网友表示赞同！
这个概念挺深刻，感觉很有实用价值。
有13位网友表示赞同！
之前遇到类似的问题，不知道有没有这种算法解决的。
有11位网友表示赞同！
对图形结构研究的人感觉会用到吧？
有13位网友表示赞同！
是不是只有在单源情况下才能用呢？多源的最短路怎么办？
有18位网友表示赞同！
这和路径规划应该有关系吧？
有19位网友表示赞同！
想了解一下它复杂度是多少啊。
有16位网友表示赞同！
感觉这个算法挺重要的，能应用到很多领域
有7位网友表示赞同！
单源最短路是什么情况？听起来很专业哦！
有16位网友表示赞同！
需要好好学习一下这方面的内容啊。
有7位网友表示赞同！
这种算法有没有什么局限性呢？
有16位网友表示赞同！
我试着应用一下看，看看能不能解决手头上的问题！
有11位网友表示赞同！
这个名字听着就感觉很厉害的样子。
有12位网友表示赞同！
以后遇到相关的问题可以参考下这个算法。
有12位网友表示赞同！
看来计算机科学真是一门深奥的学问啊！
有20位网友表示赞同！