注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

SPFA  

2009-10-24 11:23:39|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Shortest Path Faster Algorithm
用于求单源最短路径,并且当图中有负权边时,SPFA依然适用,而此时dijkstra便不适用了,而Bellman-Ford算法的复杂度又过高
用数组d记录每个结点的最短路径估计值,设立一个先进先出的队列,每次取出队首元素,对于其所指向的节点v做松弛操作,若v的d值有变化,则将其加入队尾,知道队列为空,算法结束
显然算法进行时d值越来越小,算法必然会结束
而算法复杂度认为是o(ke)
其实SPFA是Bellman-Ford算法的一种队列实现,减少了不必要的冗余计算,也有人说SPFA本来就是Bellman-Ford算法。
SPFA有两个著名的优化SLF (Small Label First)和 LLL(Large Label Last)
SLF:设要加入的节点是j,队首元素为i,若dj<di,则将j插入队首,否则插入队尾
LLL:设队首元素为i,队列中所有d值的平均值为x,若di>x则将i插入到队尾,查找下一元素,直到找到某一i使得di<=x,则将i出对进行松弛操作

虽然理论复杂度很大,SPFA的实际效率依然极高,关于SPFA、dijkstra、floyd的速度之争,是一个很有趣的问题,关于算法效率可以看下面的文章
  评论这张
 
阅读(323)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017