SPFA算法——最短路径
粗略讲讲SPFA算法的原理,SPFA算法是1994年西南交通大学段凡丁提出
是一种求单源最短路的算法
算法中需要用到的主要变量
int n; //表示n个点,从1到n标号
int s,t; //s为源点,t为终点
int d[N]; //d[i]表示源点s到点i的最短路
int p[N]; //记录路径(或者说记录前驱)
queue <int> q; //一个队列,用STL实现,当然可有手打队列,无所谓
bool vis[N]; //vis[i]=1表示点i在队列中 vis[i]=0表示不在队列中
几乎所有的最短路算法其步骤都可以分为两步
1.初始化
2.松弛操作
初始化: d数组全部赋值为INF(无穷大);p数组全部赋值为s(即源点),或者赋值为-1,表示还没有知道前驱
然后d[s]=0; 表示源点不用求最短路径,或者说最短路就是0。将源点入队;
(另外记住在整个算法中有顶点入队了要记得标记vis数组,有顶点出队了记得消除那个标记)
队列+松弛操作
读取队头顶点u,并将队头顶点u出队(记得消除标记);将与点u相连的所有点v进行松弛操作,如果能更新估计值(即令d[v]变小),那么就更新,另外,如果点v没有在队列中,那么要将点v入队(记得标记),如果已经在队列中了,那么就不用入队
以此循环,直到队空为止就完成了单源最短路的求解
SPFA可以处理负权边
定理: 只要最短路径存在,上述SPFA算法必定能求出最小值。
证明:
每次将点放入队尾,都是经过松弛操作达到的。换言之,每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路,所以每个结点都有最短路径值。因此,算法不会无限执行下去,随着d值的逐渐变小,直到到达最短路径值时,算法结束,这时的最短路径估计值就是对应结点的最短路径值。(证毕)
期望的时间复杂度O(ke), 其中k为所有顶点进队的平均次数,可以证明k一般小于等于2。
判断有无负环:
如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)
SPFA的两种写法,bfs和dfs,bfs判别负环不稳定,相当于限深度搜索,但是设置得好的话还是没问题的,dfs的话判断负环很快
int spfa_bfs(int s)
{
queue <int> q;
memset(d,0x3f,sizeof(d));
d[s]=;
memset(c,,sizeof(c));
memset(vis,,sizeof(vis)); q.push(s); vis[s]=; c[s]=;
//顶点入队vis要做标记,另外要统计顶点的入队次数
int OK=;
while(!q.empty())
{
int x;
x=q.front(); q.pop(); vis[x]=;
//队头元素出队,并且消除标记
for(int k=f[x]; k!=; k=nnext[k]) //遍历顶点x的邻接表
{
int y=v[k];
if( d[x]+w[k] < d[y])
{
d[y]=d[x]+w[k]; //松弛
if(!vis[y]) //顶点y不在队内
{
vis[y]=; //标记
c[y]++; //统计次数
q.push(y); //入队
if(c[y]>NN) //超过入队次数上限,说明有负环
return OK=;
}
}
}
} return OK; }
int spfa_dfs(int u)
{
vis[u]=;
for(int k=f[u]; k!=; k=e[k].next)
{
int v=e[k].v,w=e[k].w;
if( d[u]+w < d[v] )
{
d[v]=d[u]+w;
if(!vis[v])
{
if(spfa_dfs(v))
return ;
}
else
return ;
}
}
vis[u]=;
return ;
}
最新文章
- spring的依赖注入,为什么用接口的实现类而不是父类的继承类?
- 用 string 进行插入、替代、查找输出下标等操作
- C# 类成员备忘
- ubuntu下搭建samba服务器
- 快来玩“Gift大转盘”百分百赚好礼
- MD5 加密的两种方法
- codeforces B. Levko and Permutation 解题报告
- js checkbox
- POJ 1811 Prime Test(Miller-Rabin &; Pollard-rho素数测试)
- windows服务访问网络资源(局域网内共享的文件夹)
- tomcat设置内存大小
- 如何安装mysql-5.5.29-win32.zip
- Objective-C中的协议(Protocol)和类别(Category)
- oc随笔六:字典
- iPhone开发之全局变量的使用
- 如何自定义iOS中的控件
- 八 Appium常用方法介绍
- Appium安卓真机环境搭建
- Unity文档阅读 第二章 依赖注入
- Python基本类常用方法
热门文章
- HibernateTemplate方法的使用
- Hibernate连接池设置
- Eclipse:Could not create the view: Plug-in org.eclipse.jdt.ui was unable to load class org.eclipse.
- Vector 源码阅读
- hadoop2.3安装过程及问题解决
- JAVA 水果机游戏及编码
- (转)nginx-rtmp-module和ffmpeg搭建实时HLS切片
- 如何让你的手机U盘集PE工具、系统安装、无线破解等众多功能于一身
- deepin 安装微信与QQ
- python基础-元组