用matlab实现寻找最短路.pdf
版权申诉
175 浏览量
2023-08-15
22:50:59
上传
评论
收藏 751KB PDF 举报
。
-可编辑修改-
用 matlab 寻找赋权图中的最短路中的应用
1 引言
图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游
戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，
如迷宫问题，博弈问题等。这些古老的难题，吸引了很多学者的注意。
1847 年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发
展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的
问题时，发挥出很大的作用。在实践中，图论已成为解决自然科学，工程技术，社会科学，
军事等领域中许多问题的有力工具之一。
最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条
距离最小的路。
2 最短路
2.1 最短路的定义（short-path problem）
对最短路问题的研究早在上个世纪 60 年代以前就卓有成效了，其中对赋权图
0
ij
w
的有效算法是由荷兰著名计算机专家 E.W.Dijkstra 在 1959 年首次提出的,该算法
能够解决两指定点间的最短路,也可以求解图 G 中一特定点到其它各顶点的最短路。后来海
斯在 Dijkstra 算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的
最短路问题。因此由 Ford 提出了 Ford 算法,它能有效地解决含有负权的最短路问题。但在
剩余14页未读，继续阅读
资源评论
hhappy0123456789
- 粉丝: 61
- 资源: 5万+
