《2022年用matlab寻找赋权图中的最短路 .pdf》由会员分享，可在线阅读，更多相关《2022年用matlab寻找赋权图中的最短路 .pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、- 1 - 用 matlab寻找赋权图中的最短路专业：小组：第 22小组小组成员：课题：用 matlab 寻找赋权图中的最短路采用形式 ：集体讨论，并到图书馆搜集相关资料，进行编程，运行。最后以论文的形式表现出来。1引言图论是应用数学的一个分支， 它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究， 如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。这些古老的难题，吸引了很多学者的注意。1847 年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领
2、域的问题时，发挥出很大的作用。 在实践中， 图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条距离最小的路。2 最短路2.1 最短路的定义（short-path problem）对最短路问题的研究早在上个世纪60 年代以前就卓有成效了，若网络中的每条边都有一个数值( 长度、成本、时间等) ，则找出两节点( 通常是源节点和阱节点) 之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管路铺设、线路安装、厂区布局和设备更新等
3、，而且经常被作为一个基本的工具，用于解决其他的做优化问题。定义 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）=Pmin w（P）式中对
4、 D 中所有从 vs到 vt 的路 P最小，称 P0 是从 vs到 vt 的最短路。2.2 最短路问题算法的基本思想及其基本步骤在求解网络图上节点间最短路径的方法中，目前国内外一致公认的比较好的算法有 Dijkstra 和 Floyd 算法。这两种算法，网络被抽象为一个图论中定义的有向图或无向图， 并利用图的节点邻接矩阵记录点的关联信息。在进行图的遍历搜名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - - 2 - 索最短路径时，
5、以该矩阵为基础不断进行目标值的最小性判别，知道获得最后的优化路径。鉴于课本使用Dijkstra 算法，下面用 Floyd算法进行计算：设 A=（a）n*n 为赋权图 G=（V，E ，F）的矩阵，当 ViVj E时，aij =F（vi，vj） ，否则，取 aij =0，aij =+（ij） ，dij 表示从 vi到 vj 的点的距离， rij 表示从 vi到 vj 的点的最短路中的一个点的编号。 赋初值。对所有 i，j，dij = aij ，rij =j ，k=1，转向； 更新 dij ，rij ，对所有 i ，j ，若 dik + dkj dij , 则令 dij = dik + dkj ，r
6、ij =k，转向； 终止判断。若 dij 0,则存在一条含有顶点vi的负回路，终止；或者 k=n，终止；否则，另 k=k+1，转向。最短路线可由 rij得到。2.3 用 matlab程序实现上述算法编写程序函数程序如下：function f=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
7、=1:n)for (j=1:n)if (D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); % 更新 dij R(i,j)=k; % 更新 rijend;end;end k % 显示迭代步数 D % 显示每步迭代后的路长 R % 显示每步迭代后的路径 pd=0;for (i=1:n) % 含有负权if (D(i,j)0) pd=1;break ;end;end% 存在一条含有顶点的vi 的负回路if (pd)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -
8、第 2 页，共 3 页 - - - - - - - - - - 3 - break ;end % 存在一条负回路，终止程序end% 程序结束3 最短路的实际应用最短路问题在交通网络结构的分析，交通运输路线（公路、铁路、河流航运线、航空线、管道运输路线等）的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。最短路问题在实际中还常用于汽车导航系统以及各种应急系统等（110 报警、119 火警以及 120 医疗救护系统），这些系统一般要求计算出到出事地点的最佳路线的时间最短。 利用最短路还需要实际计算出前方的行驶路线，这就决定了最短路径问题的实现应该是高
9、效率的。根据现在发展的要求， 在城乡一体化的总体思路中， 为实现农村村村通的目标，针对农村地理分布，进行合理规划，对与优化农村交通网络，促进农村发展有重要的内容。4 结语本文将最短路理论与实际相联系，尤其是对与当前热点问题的应用，具有很重要的意义。 将实际生活中出现的安全隐患尽量降低。同时也凸显出学习与应用最短路原理的重要性。 要在平时的生活中， 注意学习中的相关联系， 以此可以提高学生学习知识的兴趣。【参考文献 】 ：1 甘应爱、田丰等 . 运筹学（第三版） . 北京 . 清华大学出版社2006.2 蒲俊等 . MATLAB6.0数学手册. 上海 . 浦东电子出版社2002 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -