图论中最短路径问题算法程序的开发1
需积分: 0 201 浏览量
2022-08-04
13:23:09
上传
评论
收藏 288KB PDF 举报
·制造业信息化·
０
引言
图论最早应用于分析电路网络， 随着科学的发展，
图论在解决运筹学， 网络理论， 信息论， 控制论， 博奕
论以及计算机科学等各个领域的问题方面， 发挥出越来
越大的作用
［１］
。图论方法直观明了、使用方便、容易掌
握
， 图论已成为解决自然科学、工程技术、社会科学、
生物技术以及经济、军事等领域中许多问题的有力工具
之一。最短路径问题
［２，３］
是网络理论中应用最广泛的问题
之一。许许多多的优化问题上可以使用这个模型
， 如设
备更新、管道铺设、线路安排、厂区布局等。
本文讨论最短路径问题的算法， 利用
Ｄｅｌｐｈｉ ７．０
语
言开发最短路径问题的算法程序
， 同时考虑了所开发的
系统用户界面友好， 便于使用， 最后利用实例进行程序
调试和验证。所开发的最短路径问题算法程序也是图论
算法平台的一个重要组成部分。
１
最短路径问题
定义： 给定一个赋权的有向图
Ｄ ＝ （Ｖ
，
Ａ）
， 记
Ｄ
中每
一条弧
ａ
ｉｊ
＝（ｖ
ｉ
，ｖ
ｊ
）
上的权为
ｗ
ｉｊ
（ａ
ｉｊ
）＝ｗ
ｉｊ
。给定
Ｄ
中一个起点
ｖ
ｓ
和
ｖ
ｔ
终点， 设
Ｐ
是
Ｄ
中从
ｖ
ｓ
到
ｖ
ｔ
的一条路， 则定义路
Ｐ
的权是
Ｐ
中所有弧的权之和。记为
ｗ（Ｐ）
， 即：
ｗ（Ｐ）＝∑ｗ
ｉｊ
又若
Ｐ
＊
是
Ｄ
图中
ｖ
ｓ
到
ｖ
ｔ
的一条路， 且满足
ｗ （Ｐ
＊
）＝
ｍｉｎ｛ ｗ（Ｐ）
∣
Ｐ
是到
ｖ
ｔ
的路
｝
。
式中对
Ｄ
的所有从
ｖ
ｓ
到
ｖ
ｔ
的路
Ｐ
取最小， 则称
Ｐ
＊
为从
ｖ
ｓ
到
ｖ
ｔ
的最短路径，
ｗ （Ｐ
＊
）
为
ｖ
ｓ
从到的最短距离。
在一个图
Ｄ＝
（
Ｖ
，
Ａ
） 中， 求从
ｖ
ｓ
到
ｖ
ｔ
的最短路径和最
短距离的方法就是最短路径问题。
２
最短路径问题算法
在一个赋权有向图中寻求最短路径的方法实际上就
是求出了从给定
ｖ
ｓ
到任一个顶点
ｖ
ｉｊ
的最短路径。
求最短路径采用标号法
， 此法是
１９５９
年由
Ｅ．Ｗ．Ｄｉ－
ｊｋｓｔｒａ
首先提出来的， 故称为
Ｄｉｊｋｓｔｒａ
算法， 此算法求解
两个固定点之间的最短路径或从一个固定点到其它所有
点之间的最短路径
， 目前被认为是求无负权网络最短路
径问题的最好方法
［４］
。但是此算法只是适合所 有的 权
ｗ
ｉｊ
≥０
的情形
［５］
。这种算法的基本思路是从起点
ｖ
ｓ
出发，
逐步向外探寻最短路径， 执行过程中， 给每一个顶点
ｖ
ｊ
标号， 若
｛ｖ
ｓ
，
ｖ
１
，
…
，ｖ
ｊ
｝
是从
ｖ
ｓ
到
ｖ
ｊ
的最短路径， 则
｛ｖ
ｓ
，
ｖ
１
，
…
，ｖ
ｋ
｝
是从
ｖ
ｓ
到
ｖ
ｋ
的最短路径。
所谓的标号法采用两种标号
：
Ｔ
标号和
Ｐ
标号， 其
中
Ｔ
为临时标号，
Ｐ
为永久标号， 给
ｖ
ｉ
一个
Ｐ
标号时，
表示从
ｖ
ｓ
到
ｖ
ｉ
点的最短路径，
ｖ
ｉ
点的标号不再改变。给
ｖ
ｉ
一个
Ｔ
标号时， 表示从
ｖ
ｓ
到
ｖ
ｉ
点的估计最短路径权的
上界， 是临时的标号， 没有得到
Ｐ
标号的 就都 是
Ｔ
标
号。所以算法的关键就是把每一点的
Ｔ
标号改为
Ｐ
标
号
， 直到终点变为
Ｐ
标号时算法结束。
Ｄｉｊｋｓｔｒａ
算法的具体步骤：
①
给
ｖ
ｓ
以
Ｐ
标号，
Ｐ
（
ｖ
ｓ
）
＝０
，
其余的各点为
Ｔ
标号，
Ｔ
（
ｖ
ｉ
）
＝＋∞
；
②
若
ｖ
ｉ
点为刚得到
Ｐ
标
号的点
， 考虑这样的点
ｖ
ｊ
： （
ｖ
ｉ
，
ｖ
ｊ
） 属于
Ａ
， 且
ｖ
ｊ
为
Ｔ
标号。对
于
ｖ
ｊ
进行修改：
Ｔ
（
ｖ
ｊ
）
＝ｍｉｎ｛ Ｔ
（
ｖ
ｉ
） ，
Ｐ
（
ｖ
ｉ
）
＋ｌ
ｉｊ
｝
；
③
比较所有的
Ｔ
标号的点， 把最小者改为
Ｐ
标号， 即：
Ｐ
（
ｖ
ｉ
）
＝ ｍｉｎ｛Ｔ
（
ｖ
ｉ
）
｝
图论中最短路径问题算法程序的开发
张俊杰
１
， 杨艳丽
２
， 曹 岩
３
， 白 瑀
３
， 蔺麦田
３
（
１．
华为技术有限公司， 广东 深圳
５１８０２７
；
２．
深圳大学 信息工程学院计算机系， 广东 深圳
５１８０６０
；
３．
西安工业大学 机电工程学院， 陕西 西安
７１００３２
）
摘 要：
研究了图论中的最短路径问题算法程序的开发。首先， 介绍了最短路径问题的概念和最短路径
问题的算法。然后在
Ｄｅｌｐｈｉ ７．０
环境下开发目前最短路径问题算法的流程。最后， 通过实例对最
短路径问题的算法程序进行了验证。所开发的算法程序直观简捷
， 方便工程人员的使用。
关键词：
图论； 最短路径； 算法；
Ｄｅｌｐｈｉ
中图分类号：
Ｏ１５７．５
文献标识码：
Ａ
文章编号：
１００２－ ６６７３
（
２００８
）
０１
－ １０３－ ０２
收稿日期：
２００７－ ０９－ １８
作者简介： 张俊杰 （
１９６３－
） ， 男， 山西阳曲人， 工学博士。
主要研究方向
： 通信设备故障监 测与诊断、通信设备内的
控制与管理技术等。发表文章
１０
余篇； 杨艳丽 （
１９６４－
） ，
女， 江苏溧阳人， 副教授， 工学博士， 硕士生导师。主要研
究方向
： 智能控制、
ＣＡＤ＼ ＣＡＭ
， 发表文章
１０
余篇。
Ｖｏｌ．２１，Ｎｏ．１
Ｊａｎ．，２００８
第
２１
卷第
１
期
２００８
年
１
月
机电产品开发与创新
Ｄｅｖｅｌｏｐｍｅｎｔ ＆ Ｉｎｎｏｖａｔｉｏｎ ｏｆ Ｍａｃｈｉｎｅｒｙ ＆ Ｅｌｅｃｔｒｉｃａｌ Ｐｒｏｄｕｃｔｓ
１０３
梁肖松
- 粉丝: 26
- 资源: 300
评论0