博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
spfa算法详解
阅读量:5874 次
发布时间:2019-06-19

本文共 505 字,大约阅读时间需要 1 分钟。

spfa的算法思想(动态逼近法):

设立一个先进先出的队列q用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。

松弛操作的原理是著名的定理:“三角形两边之和大于第三边”,在信息学中我们叫它三角不等式。所谓对结点i,j进行松弛,就是判定是否dis[j]>dis[i]+w[i,j],如果该式成立则将dis[j]减小到dis[i]+w[i,j],否则不动。
下面举一个实例来说明SFFA算法是怎样进行的:

和广搜bfs的区别:

SPFA 在形式上和广度(宽度)优先搜索非常类似,不同的是bfs中一个点出了队列就不可能重新进入队列,但是SPFA中一个点可能在出队列之后再次被放入队列,也就是一个点改进过其它的点之后,过了一段时间可能本身被改进(重新入队),于是再次用来改进其它的点,这样反复迭代下去。

算法图解

这里写图片描述

这里写图片描述

转载于:https://www.cnblogs.com/readlearn/p/10806400.html

你可能感兴趣的文章
js replace,正则截取字符串内容
查看>>
socket
查看>>
Highcharts使用表格数据绘制图表
查看>>
Thinkphp5笔记三:创建基类
查看>>
LNMP之编译安装PHP出现的问题
查看>>
hdu5373
查看>>
4.单链表的创建和建立
查看>>
testng生成报告 testng-xslt 美化测试报告
查看>>
Android 好看的搜索界面,大赞Animation
查看>>
查询反模式 - GroupBy、HAVING的理解
查看>>
[转]动态加载javascript
查看>>
【协议】5、gossip 协议
查看>>
基于配置文件的redis的主从复制
查看>>
hasura graphql 角色访问控制
查看>>
springmvc中controller内方法跳转forward?redirect?
查看>>
C#委托,事件理解入门 (译稿)转载
查看>>
容器的end()方法
查看>>
[转] Agile Software Development 敏捷软件开发
查看>>
HDU 1007 Quoit Design (最小点对,模板题)
查看>>
Windows Phone 7 自定义事件
查看>>