北京大学acm暑期课讲义-spfa算法
7页SPFA算法,SPFA 全称 Shortest Path Faster Algorithm 基本应用为快速求解单源最短路,Spfa算法可以说是Bellman-ford算法的改进版.spfa是利用队列来动态更新最小值.,SPFA算法实现,设Dist代表S到I点的当前最短距离,Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+,只有DistS=0,Fa全部为0。 维护一个队列,里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。,SPFA算法实现,每次迭代,取出队头的点v,依次枚举从v出发的边v-u,设边的长度为len,判断Distv+len是否小于Distu,若小于则改进Distu,将Fau记为v,并且由于S到u的最短距离变小了,有可能u可以改进其它的点,所以若u不在队列中,就将它放入队尾。这样一直迭代下去直到队列变空,也就是S到所有节点的最短距离都确定下来,结束算法。若一个点最短路被改进的次数达到n ,则有负权环。可以用spfa算法判断图有无负权环,SPFA算法实现,在Bellman-Ford算法中,要是某个点的最短路径估计值更新了,那么我们必须对所有边的终点再做一次松弛操作;在SPFA算法中,某个点的最短路径估计值更新,只有以该点为起点的边指向的终点需要再做一次松弛操作。在极端情况下,后者的效率将是前者的n倍。 在平均情况下,SPFA算法的期望时间复杂度为O(E)。,例题: POJ 2387 POJ 3256,
《北京大学acm暑期课讲义-spfa算法》由会员xzh****18分享,可在线阅读,更多相关《北京大学acm暑期课讲义-spfa算法》请在金锄头文库上搜索。
爱心树活动教案
世界文化之旅0
七年级学年知识归纳
七年级历史下册第二单元第12课《蒙古的兴起和元朝的建立》课件人教新课标版
一片美丽的叶子
非谓语动词 (6)
[中学联盟]江苏省太仓市第二中学七年级英语上册教学课件:Unit3READING1 (2)
“数与代数”教材修订说明
2014年7月师院培训
字理教学快捷入门之一20140521s
议论文写作指导之新材料作文审题立意 (2)
压缩语段 (2)
琵琶行课件 (2)
2014年各年级的教学计划和建议
(苏教版)五年级数学下册找规律第二课时
秋姑娘的信 (5)
苏教版数学五年级上册《复式条形统计图》课件 (2)
【名校课时通】2014届九年级化学全册第二单元探秘水世界第三节原子的构成名师教学课件鲁教版
《逻辑与语文》课件2
《检阅》[1]
2024-03-27 33页
2024-03-27 32页
2024-03-27 34页
2024-03-27 31页
2024-03-27 33页
2024-03-27 33页
2024-03-27 31页
2024-03-27 34页
2024-03-27 31页
2024-03-27 28页