位置: 编程技术 - 正文

PHP实现的迪科斯彻(Dijkstra)最短路径算法实例(phpdie)

编辑:rootadmin

推荐整理分享PHP实现的迪科斯彻(Dijkstra)最短路径算法实例(phpdie),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:phpdesk,php dio,php des,php dicom,php _dir_,php di,php di,php dio,内容如对您有帮助,希望把文章链接给更多的朋友!

本文实例讲述了PHP实现的迪科斯彻(Dijkstra)最短路径算法。分享给大家供大家参考,具体如下:

一、待解决问题

单源最短路径问题,在给定有向图中求一个顶点(单源顶点)到其他所有顶点的最短路径问题。在下图中,每条边上有一个权值,希望求解A到所有其他顶点(B/C/D/E/F/G)的最短路径。

二、问题分析(最短路径的子结构同样最优性)

如果P(A,G)是从顶点A到G的最短路径,假设D和F是这条路径上的中间点,那么P(D,F)一定时从D到F的最短路径。如果P(D,F)不是D到F的最短路径,那必然存在某一个节点M的另一条D到F的路径可以使P(A,B...M...F,G)比P(A,G)小,自相矛盾。

有了这样的性质,我们可以了解Dijkstra算法。

三、Dijkstra算法

Dijkstra 算法,又叫迪科斯彻算法(Dijkstra),又称为单源最短路径算法,所谓单源是在一个有向图中,从一个顶点出发,求该顶点至所有可到达顶点的最短路径问题。 问题描述为设G=(V,E)是一个有向图,V表示顶点,E表示边。它的每一条边(i,j)属于E,都有一个非负权W(I,j),在G中指定一个结点v0,要求把从v0到G的每一个接vj(vj属于V)的最短有向路径找出来(或者指出不存在)。 Dijstra算法是运用贪心的策略,从源点开始,不断地通过相联通的点找出到其他点的最短距离。

Dijkstra的贪心应用在他利用(二)中的性质,不断地选取“最近”的节点并试探每个节点的所有可能存在链接,以起始点为中心向外层层扩展,直到扩展到终点为止。对于源点A,逐步扩展,根据dist[j]=min{dist[j],dist[i]+matrix[i][j]}更新与i直接相邻的顶点信息。

算法描述

PHP实现的迪科斯彻(Dijkstra)最短路径算法实例(phpdie)

1)算法思想:

设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

2)算法步骤:

a.初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则<u,v>正常有权值,若u不是v的出边邻接点,则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。

c.以k为新考虑的中间点,修改U中与k相邻的各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值为顶点k的距离加上k与u边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

四、算法PHP实现

调用类:

执行结果:

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《PHP基本语法入门教程》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》及《php查找技巧与方法总结》

希望本文所述对大家PHP程序设计有所帮助。

PHP实现广度优先搜索算法(BFS,Broad First Search)详解 本文实例讲述了PHP实现广度优先搜索算法。分享给大家供大家参考,具体如下:广度优先搜索的算法思想Breadth-FirstTraversal广度优先遍历是连通图的一种

PHP实现深度优先搜索算法(DFS,Depth First Search)详解 本文实例讲述了PHP实现深度优先搜索算法。分享给大家供大家参考,具体如下:深度优先搜索的实现原理:实现代码:phpclassSearch_Method{//无向图的数组

PHP中使用jQuery+Ajax实现分页查询多功能操作(示例讲解) 1.首先做主页面Ajax_pag.php代码如下:!DOCTYPEhtmlhtmlheadmetacharset="UTF-8"titleAjax做分页/titlescriptsrc="bootstrap/js/jquery-1..2.min.js"/scriptscriptsrc="Ajax_pag.js"/scriptscriptsr

标签: phpdie

本文链接地址:https://www.jiuchutong.com/biancheng/282901.html 转载请保留说明!

上一篇:PHP环形链表实现方法示例(环形链表入口节点)

下一篇:PHP实现广度优先搜索算法(BFS,Broad First Search)详解(广度优先算法代码)

  • 从租计征房产税低于从价计征房产税
  • 小规模纳税人到底能不能收专票
  • 免税收入不征税收入有哪些
  • 收到发票冲红怎么做分录
  • 季报利润总额是填本季度金额还是本年累计数
  • 公司提供住宿员工在外居住出现问题
  • 免税店含增值税吗
  • 配件的出口是否可以免抵退?
  • 工资费用分配表属于什么凭证
  • 从业人数和资产总额是灰色
  • 无形资产是金融性资产还是经营性资产
  • 契税晚交有什么影响
  • 预收款开票的税务处理
  • 货物运输企业在运输货物时应当尽可能采用
  • 股息利高的股票
  • 发票超过2个月可以报销吗
  • 营改增后哪些进项不能抵扣
  • 地税没报税怎么办
  • 出口退税生产企业增值税附加税怎么申报
  • 资产负债表和业务活动表勾稽关系不对怎么查
  • 税款所属期是什么意思举例子
  • 2019年核定征收税率表
  • 营改增后的劳务费怎么开
  • 培训费开发票明细为会议费如何做账?
  • 财务负责人的岗位
  • 怎么添加一个
  • mac怎么分区硬盘分区
  • 文件夹属性没有安全
  • 事业单位租赁收入的处理
  • 单位支付安装天然气费
  • 银行多收的开户费怎么办
  • win7安装包下载
  • 财务管理公司属于什么行业类别
  • 计提摊销的分录
  • anaconda虚拟机
  • 销售方红字发票账务处理?
  • php通过url传递参数
  • php实现图片上传到网页显示
  • session跨域导致失效
  • 生产部门使用的各种机器设备属于什么会计科目
  • 浏览器打开域名怎么设置
  • sql server备份数据还原不了怎么办
  • 织梦怎么建站
  • mysql子查询关键字
  • 金税四期对企业影响
  • 中餐补助
  • 所得税调增调减技巧
  • 企业收到合同保险怎么办
  • 小规模差额征税的账务处理
  • 库存,收入,支出,进货
  • 营业外收支的账户有哪些
  • 收到投资款如何声明
  • 计提医疗保险费的会计分录
  • 项目上工人死亡赔偿
  • 库存商品暂估入库可以结转成本吗
  • 公司员工垫付款项
  • 汇算清缴调增的工资怎么做账
  • 固定资产错记到费用了怎么办
  • 建筑施工企业劳务费怎么入成本
  • 工程款可以转入存折里吗怎么转
  • 费用票成本票有哪些
  • 会计往来账如何记账
  • 存货的总账和明细账区别
  • mysql 数据修改
  • 卸载微信后重新登录微信怎么恢复之前的数据
  • Linux系统中文件的文件名存储在文件所在的目录
  • console打开
  • 怎么激活win7旗舰版系统
  • pkg-config命令
  • centos7自签名证书
  • linux实用技巧
  • 微软windows10正版
  • opengl矩形
  • js基于贪心算法实验报告
  • 关于echo的名字
  • jquery控制样式
  • 鼠标悬停时的动画效果
  • 宁波无犯罪证明能当场拿到吗
  • 武汉车船使用税收费标准
  • 财政临时工是什么
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设