没有合适的资源?快使用搜索试试~ 我知道了~
SPFA——Shortest Path Faster Algorithm,它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。
资源推荐
资源详情
资源评论
spfa 算法:
算法流程
算法大致流程是用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元
素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。直到队列
为空时算法结束。
这个算法,简单的说就是队列优化的 bellman-ford,利用了每个点不会更新次数太多的特
点发明的此算法
SPFA——Shortest Path Faster Algorithm,它可以在 O(kE)的时间复杂度内求出源点
到其他所有点的最短路径,可以处理负边。SPFA 的实现甚至比 Dijkstra 或者
Bellman_Ford 还要简单:
设 Dist 代表 S 到 I 点的当前最短距离,Fa 代表 S 到 I 的当前最短路径中 I 点之前的一个点
的编号。开始时 Dist 全部为+∞,只有 Dist[S]=0,Fa 全部为 0。
维护一个队列,里面存放所有需要进行迭代的点。初始时队列中只有一个点 S。用一个布
尔数组记录每个点是否处在队列中。
每次迭代,取出队头的点 v,依次枚举从 v 出发的边 v->u,设边的长度为 len,判断
Dist[v]+len 是否小于 Dist[u],若小于则改进 Dist[u],将 Fa[u]记为 v,并且由于 S 到
u 的最短距离变小了,有可能 u 可以改进其它的点,所以若 u 不在队列中,就将它放入队
尾。这样一直迭代下去直到队列变空,也就是 S 到所有的最短距离都确定下来,结束算法。
若一个点入队次数超过 n,则有负权环。
SPFA 在形式上和宽度优先搜索非常类似,不同的是宽度优先搜索中一个点出了队列就不
可能重新进入队列,但是 SPFA 中一个点可能在出队列之后再次被放入队列,也就是一个
点改进过其它的点之后,过了一段时间可能本身被改进,于是再次用来改进其它的点,这
样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为 k,有办法证
明对于通常的情况,k 在 2 左右。
算法的描述:
void spfa(s); //求单源点 s 到其它各顶点的最短距离
for i=1 to n do { dis[i]=∞; vis[i]=false; } //初始化每点到 s 的
距离,不在队列
dis[s]=0; //将 dis[源点]设为 0
vis[s]=true; //源点 s 入队列
head=0; tail=1; q[tail]=s; //源点 s 入队, 头尾指针赋初值
资源评论
qq_41183429
- 粉丝: 0
- 资源: 6
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功