C语言 vim复制 阿里云 tsql ios5 vue滑动事件 jquery遍历元素 软件测试实战项目 bootstrap中文api文档 python平方函数 python编程题 python指令 python中的map函数 python分析 python时间戳 python导入文件 java运算符 javasocket通信 java查看数据类型 java怎么安装 java时间类型 java线程停止 灼热峡谷 音频频谱分析软件 p6软件 ansys安装教程 pr怎么放大视频画面 苏拉玛起义的任务线 jdk9下载 python数组赋值 eagle软件 看图软件cad linux格式化硬盘 dota2控制台 联盟练级路线 启用宏在哪里设置 dbgview iosps腹肌 win10工作组 取小数点后两位函数
当前位置: 首页 > 学习教程  > 编程语言

[小王的学习笔记]SPFA算法

2020/9/19 13:40:46 文章标签:

SPFA算法全名shortest path faster algorithm,最短路径更快速算法,它是与Bellman-ford算法进行比较,时间复杂度从O(n^3)或者O(nm)变成O(km),k为每个结点平均入队次数,是一个经验数,一般情况下k为2

由于Bellman-ford算法将会有大规模的冗余比较,所以我们想要尽可能的减少节点入队次数,从而降低复杂度。我们用队列实现,可以用stl自带的queue来实现,也可以用一个int数组,用head和tail指针来控制队列的操作。

算法操作:每次将队首取出来,松弛与它相连的点,如果松弛成功,判断该点是否已经在队列里了,如果在队列里了,我们就没必要入队,如果不在队列里,我们将该点入队。

void spfa(int u0)
{
	memset(dist,63,sizeof(dist)); 
	memset(inq,0,sizeof(inq));
	dist[u0] = 0;
 	queue<int> q;
	q.push(u0);
	inq[u0] = 1;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		inq[u] = 0;
		for(int i = h[u]; i != -1; i = e[i].next){
			int v = e[i].v;
			if(dist[v] > dist[u] + e[i].w){
				dist[v] = dist[u] + e[i].w;
				if(!inq[v]){
					q.push(v);
					inq[v] = 1;
				}
			}
		}
	}
}

这就是SPFA算法的主体,我这里是用的邻接表存图,用邻接矩阵也可以实现,只需要修改一下相关部分的内容。

练习题:
hihoCoder 1093 : 最短路径·三:SPFA算法
luogu P3385 【模板】负环


本文链接: http://www.dtmao.cc/news_show_200055.shtml

附件下载

上一篇:算法-减治法

下一篇:upx脱壳日记

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?