当前位置: 首页> 教育> 高考 > 可视化app开发工具安卓版_网络设计的目的是_平台营销_湖南企业竞价优化公司

可视化app开发工具安卓版_网络设计的目的是_平台营销_湖南企业竞价优化公司

时间:2025/7/11 23:22:45来源:https://blog.csdn.net/2301_81247182/article/details/146191907 浏览次数:0次
可视化app开发工具安卓版_网络设计的目的是_平台营销_湖南企业竞价优化公司

SPFA算法其实是对Bellman-ford算法的优化,Bellman-ford算法更新最短路是采用的是遍历每一条边,找到最短的边进行更新d[v]=min(d[v],d[u]+w(u,v)),由 d[v]=min(d[v],d[u]+w(u,v))可知只有当  d[ u ]变小时才有可能更新,所以用一个队列存储每次变化的点,便于更新操作

算法步骤

初始化:设源点为s,将源点s加入队列,初始化源点到自身的距离为0,即d[s]=0,其他点到源点的距离初始化为无穷大∞。

队列操作与松弛:从队列中取出一个顶点u,遍历u的所有邻接顶点v,如果d[v]>d[u]+w(u,v)(其中w(u,v)是边(u,v)的权值),则更新d[v]=d[u]+w(u,v),且若v不在队列中,将v加入队列。

重复操作:重复步骤 2,直到队列为空。

判断负环:在执行过程中,如果某个顶点入队次数超过n−1次(n为图中顶点的个数),则说明图中存在负环,不存在从源点到其他顶点的最短路径。

例:

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 impossible

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 mm 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 impossible

数据范围

1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。

输入样例:
3 3
1 2 5
2 3 -3
1 3 4
输出样例:
2

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>using namespace std;typedef pair<int,int >PII;const int N = 1e6+10;
int h[N],w[N],ne[N],e[N],idx;
bool st[N];//标记点是否存在队列当中
int dist[N];
int n,m;void add(int x,int y,int z){e[idx]=y;w[idx]=z;ne[idx]=h[x];h[x]=idx++;
}void spfa(){memset(dist,0x3f,sizeof dist);dist[1]=0;queue<int> q;q.push(1);st[1]=true;//将1号点加入队列并标记为已存在while(q.size()){int t=q.front();q.pop();//每次取出队头元素并删除队头元素st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){//遍历t的所有出边进行更新int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];if(!st[j]){q.push(j);st[j]=true;}}}}}int main(){memset(h,-1,sizeof h);scanf("%d%d",&n,&m);while(m--){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);}spfa();if(dist[n]==0x3f3f3f3f)printf("impossible");else printf("%d",dist[n]);return 0;
}

关键字:可视化app开发工具安卓版_网络设计的目的是_平台营销_湖南企业竞价优化公司

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: