用matlab实现寻找最短路.docx
- 文档编号:10600380
- 上传时间:2023-05-26
- 格式:DOCX
- 页数:11
- 大小:25.49KB
用matlab实现寻找最短路.docx
《用matlab实现寻找最短路.docx》由会员分享,可在线阅读,更多相关《用matlab实现寻找最短路.docx(11页珍藏版)》请在冰点文库上搜索。
用matlab实现寻找最短路
用matlab寻找赋权图中的最短路中的应用
1引言
图论是应用数学的一个分支,它的概念和结果来源都非常广泛,最早起源于一些数学游戏的难题研究,如欧拉所解决的格尼斯堡七桥问题,以及在民间广泛流传的一些游戏的难题,如迷宫问题,博弈问题等。
这些古老的难题,吸引了很多学者的注意。
1847年,图论应用于分析电路网络,这是它最早应用于工程科学,以后随着科学的发展,图论在解决运筹学,网络理论,信息论,控制论,博弈论以及计算机科学等各个领域的问题时,发挥出很大的作用。
在实践中,图论已成为解决自然科学,工程技术,社会科学,军事等领域中许多问题的有力工具之一。
最短路问题是图论理论中的经典问题,寻找最短路径就是在指定网络中两节点间找一条距离最小的路。
2最短路
2.1最短路的定义(short-pathproblem)
对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图
的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。
后来海斯在Dijkstra算法的基础之上提出了海斯算法。
但这两种算法都不能解决含有负权的图的最短路问题。
因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。
但在现实生活中,我们所遇到的问题大都不含负权,所以我们在
的情况下选择Dijkstra算法。
若网络中的每条边都有一个数值(长度、成本、时间等),则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。
最短路问题是网络理论解决的典型问题之一,它不仅可以直接应用于解决生产实际的许多问题,如管路铺设、线路安装、厂区布局和设备更新等,而且经常被作为一个基本的工具,用于解决其他的做优化问题。
定义1:
若图G=G(V,E)中个边[vi,vj]都赋有一个实数wij,则称这样的图G为赋权图,wij称为边[vi,vj]上的权。
定义2:
给定一个赋权有向图,即给一个有向图D=(V,A),对每一个弧a=(vi,vj),相应地有权w(a)=wij,又给定D中的两个顶点vs,vt。
设P是D中从vs到vt的一条路,定义路P的权是P中所有弧的权之和,记为w(P)。
最短路问题就是要在所有从vs到vt的路中,求一条权最小的路,即求一条从vs到vt的路P0,使w(P0)=
w(P)式中对D中所有从vs到vt的路P最小,称P0是从vs到vt的最短路。
2.2最短路问题算法的基本思想及其基本步骤
在求解网络图上节点间最短路径的方法中,目前国内外一致公认的比较好的算法有Dijkstra和Floyd算法。
这两种算法,网络被抽象为一个图论中定义的有向图或无向图,并利用图的节点邻接矩阵记录点的关联信息。
在进行图的遍历搜索最短路径时,以该矩阵为基础不断进行目标值的最小性判别,知道获得最后的优化路径。
鉴于课本使用Dijkstra算法,下面用Floyd算法进行计算:
设A=(a)n*n为赋权图G=(V,E,F)的矩阵,当ViVj∈E时,aij=F(vi,vj),否则,取aij=0,aij=+∞(i≠j),dij表示从vi到vj的点的距离,rij表示从vi到vj的点的最短路中的一个点的编号。
1赋初值。
对所有i,j,dij=aij,rij=j,k=1,转向②;
2更新dij,rij,对所有i,j,若dik+dkj 3终止判断。 若dij<0,则存在一条含有顶点vi的负回路,终止;或者k=n,终止;否则,另k=k+1,转向②。 最短路线可由rij得到。 2.3用matlab程序实现上述算法 编写程序函数程序如下: functionf=shortpath(n,A) clear; n=input('请输入矩阵的阶n='); A=input('请输入赋权图对应的n阶矩阵A=');%顶点之间不通时,用inf表示(MATLAB中,inf表示无穷) D=A;%赋初值 for(i=1: n) for(j=1: n) R(i,j)=j; end; end%赋路径初值 for(k=1: n) for(i=1: n) for(j=1: n) if(D(i,k)+D(k,j) D(i,j)=D(i,k)+D(k,j);%更新dij R(i,j)=k;%更新rij end; end; end k%显示迭代步数 D%显示每步迭代后的路长 R%显示每步迭代后的路径 pd=0; for(i=1: n)%含有负权 if(D(i,j)<0) pd=1; break; end; end%存在一条含有顶点的vi的负回路 if(pd) break; end%存在一条负回路,终止程序 end%程序结束 下面用一个实际的例子进行一下函数实际运算: 例: 求解下赋权图中任意两点中的最短路。 V16V4 26538 V08V21V56v7 17243 V39V5 用matlab函数运行以后,运行结果如下: 请输入矩阵的阶n=8 请输入赋权图对应的n阶矩阵A=[0281infinfinfinf;206inf1infinfinf;8607512inf;1inf70infinf9inf;inf15inf03inf8;infinf1inf3046;infinf29inf403;infinfinfinf8630] k=1 D= 0281InfInfInfInf 20631InfInfInf 8607512Inf 1370InfInf9Inf Inf15Inf03Inf8 InfInf1Inf3046 InfInf29Inf403 InfInfInfInf8630 R= 12345678 12315678 12345678 11345678 12345678 12345678 12345678 12345678 k=2 D= 02813InfInfInf 20631InfInfInf 8607512Inf 13704Inf9Inf 315403Inf8 InfInf1Inf3046 InfInf29Inf403 InfInfInfInf8630 R= 12342678 12315678 12345678 11342678 22325678 12345678 12345678 12345678 k=3 D= 02813910Inf 2063178Inf 8607512Inf 1370489Inf 31540378 97183036 108297303 InfInfInfInf8630 R= 12342338 12315338 12345678 11342378 22325638 33335638 33343378 12345678 k=4 D= 02813910Inf 2063178Inf 8607512Inf 1370489Inf 31540378 97183036 108297303 InfInfInfInf8630 R= 12342338 12315338 12345678 11342378 22325638 33335638 33343378 12345678 k=5 D= 0281361011 20631489 860751213 137047912 31540378 64173036 108297303 11913128630 R= 12342535 12315535 12345675 11342575 22325638 55355638 33343378 55555678 k=6 D= 027136911 20531479 75074127 137047912 31440368 64173036 97296303 1197128630 R= 12642565 12615565 66346676 11342575 22625668 55355638 66346378 55655678 k=7 D= 027136911 20531479 75074125 137047912 31440368 64173036 97296303 1195128630 R= 12642565 12615565 66346677 11342575 22625668 55355638 66346378 55755678 k=8 D= 027136911 20531479 75074125 137047912 31440368 64173036 97296303 1195128630 R= 12642565 12615565 66346677 11342575 22625668 55355638 66346378 55755678 注: 上例中是用一个无向赋权图,对与有向赋权图只需要把反向的定义为无穷大(在matlab中即用inf代替不能到达的情况),一样可以调用上述函数程序进行运算。 3最短路的实际应用 ●最短路问题在交通网络结构的分析,交通运输路线(公路、铁路、河流航运线、航空线、管道运输路线等)的选择,通讯线路的建造与维护,运输货流的最小成本分析,城公共交通网络的规划等,都有直接应用的价值。 ●最短路问题在实际中还常用于汽车导航系统以及各种应急系统等(110报警、119火警以及120医疗救护系统),这些系统一般要求计算出到出事地点的最佳路线的时间最短。 利用最短路还需要实际计算出前方的行驶路线,这就决定了最短路径问题的实现应该是高效率的。 ●根据现在发展的要求,在城乡一体化的总体思路中,为实现农村村村通的目标,针对农村地理分布,进行合理规划,对与优化农村交通网络,促进农村发展有重要的内容。 4结语 本文将最短路理论与实际相联系,尤其是对与当前热点问题的应用,具有很重要的意义。 将实际生活中出现的安全隐患尽量降低。 同时也凸显出学习与应用最短路原理的重要性。 要在平时的生活中,注意学习中的相关联系,那样会对学习产生更大的兴趣。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- matlab 实现 寻找 短路