用matlab实现寻找最短路.docx

用matlab寻找赋权图中的最短路中的应用1 引言图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。这些古老的难题，吸引了很多学者的注意。1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出很大的作用。在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条距离最小的路。2 最短路2.1 最短路的定义（short-path problem）对最短路问题的研究早在上个世纪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 =+（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 ，rij =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=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; %更新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 %程序结束下面用一个实际的例子进行一下函数实际运算：例：求解下赋权图中任意两点中的最短路。V1 6 V426538V08V21V56v717243V39 V5 用matlab函数运行以后，运行结果如下：请输入矩阵的阶n=8请输入赋权图对应的n阶矩阵A=0 2 8 1 inf inf inf inf;2 0 6 inf 1 inf inf inf;8 6 0 7 5 1 2 inf;1 inf 7 0 inf inf 9 inf;inf 1 5 inf 0 3 inf 8;inf inf 1 inf 3 0 4 6;inf inf 2 9 inf 4 0 3;inf inf inf inf 8 6 3 0k =1D = 0 2 8 1 Inf Inf Inf Inf 2 0 6 3 1 Inf Inf Inf 8 6 0 7 5 1 2 Inf 1 3 7 0 Inf Inf 9 Inf Inf 1 5 Inf 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6 Inf Inf 2 9 Inf 4 0 3 Inf Inf Inf Inf 8 6 3 0R = 1 2 3 4 5 6 7 8 1 2 3 1 5 6 7 8 1 2 3 4 5 6 7 8 1 1 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8k =2D = 0 2 8 1 3 Inf Inf Inf 2 0 6 3 1 Inf Inf Inf 8 6 0 7 5 1 2 Inf 1 3 7 0 4 Inf 9 Inf 3 1 5 4 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6 Inf Inf 2 9 Inf 4 0 3 Inf Inf Inf Inf 8 6 3 0R = 1 2 3 4 2 6 7 8 1 2 3 1 5 6 7 8 1 2 3 4 5 6 7 8 1 1 3 4 2 6 7 8 2 2 3 2 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8k =3D = 0 2 8 1 3 9 10 Inf 2 0 6 3 1 7 8 Inf 8 6 0 7 5 1 2 Inf 1 3 7 0 4 8 9 Inf 3 1 5 4 0 3 7 8 9 7 1 8 3 0 3 6 10 8 2 9 7 3 0 3 Inf Inf Inf Inf 8 6 3 0R = 1 2 3 4 2 3 3 8 1 2 3 1 5 3 3 8 1 2 3 4 5 6 7 8 1 1 3 4 2 3 7 8 2 2 3 2 5 6 3 8 3 3 3 3 5 6 3 8 3 3 3 4 3 3 7 8 1 2 3 4 5 6 7 8k =4D = 0 2 8 1 3 9 10 Inf 2 0 6 3 1 7 8 Inf 8 6 0 7 5 1 2 Inf 1 3 7 0 4 8 9 Inf 3 1 5 4 0 3 7 8 9 7 1 8 3 0 3 6 10 8 2 9 7 3 0 3 Inf Inf Inf Inf 8 6 3 0R = 1 2 3 4 2 3 3 8 1 2 3 1 5 3 3 8 1 2 3 4 5 6 7 8 1 1 3 4 2 3 7 8 2 2 3 2 5 6 3 8 3 3 3 3 5 6 3 8 3 3 3 4 3 3 7 8 1 2 3 4 5 6 7 8k =5D = 0 2 8 1 3 6 10 11 2 0 6 3 1 4 8 9 8 6 0 7 5 1 2 13 1 3 7 0 4 7 9 12 3 1 5 4 0 3 7 8 6 4 1 7 3 0 3 6 10 8 2 9 7 3 0 3 11 9 13 12 8 6 3 0R = 1 2 3 4 2 5 3 5 1 2 3 1 5 5 3 5 1 2 3 4 5 6 7 5 1 1 3 4 2 5 7 5 2 2 3 2 5 6 3 8 5 5 3 5 5 6 3 8 3 3 3 4 3 3 7 8 5 5 5 5 5 6 7 8k = 6D = 0 2 7 1 3 6 9 11 2 0 5 3 1 4 7 9 7 5 0 7 4 1 2 7 1 3 7 0 4 7 9 12 3 1 4 4 0 3 6 8 6 4 1 7 3 0 3 6 9 7 2 9 6 3 0 3 11 9 7 12 8 6 3 0R = 1 2 6 4 2 5 6 5 1 2 6 1 5 5 6 5 6 6 3 4 6 6 7 6 1 1 3 4 2 5 7 5 2 2 6 2 5 6 6 8 5 5 3 5 5 6 3 8 6 6 3 4 6 3 7 8 5 5 6 5 5 6 7 8k =7D = 0 2 7 1 3 6 9 11 2 0 5 3 1 4 7 9 7 5 0 7 4 1 2 5 1 3 7 0 4 7 9 12 3 1 4 4 0 3 6 8 6 4 1 7 3 0 3 6 9 7 2 9 6 3 0 3 11 9 5 12 8 6 3 0R = 1 2 6 4 2 5 6 5 1 2 6 1 5 5 6 5 6 6 3 4 6 6 7 7 1 1 3 4 2 5 7 5 2 2 6 2 5 6 6 8 5 5 3 5 5 6 3 8 6 6 3 4 6 3 7 8 5 5 7 5 5 6 7 8k = 8D = 0 2 7 1 3 6 9 11 2 0 5 3 1 4 7 9 7 5 0 7 4 1 2 5 1 3 7 0 4 7 9 12 3 1 4 4 0 3 6 8 6 4 1 7 3 0 3 6 9 7 2 9 6 3 0 3 11 9 5 12 8 6 3 0R = 1 2 6 4 2 5 6 5 1 2 6 1 5 5 6 5 6 6 3 4 6 6 7 7 1 1 3 4 2 5 7 5 2 2 6 2 5 6 6 8 5 5 3 5 5 6 3 8 6 6 3 4 6 3 7 8 5 5 7 5 5 6 7 8注：上例中是用一个无向赋权图，对与有向赋权图只需要把反向的定义为无穷大（在matlab中即用inf代替不能到达的情况），一样可以调用上述函数程序进行运算。3 最短路的实际应用 最短路问题在交通网络结构的分析，交通运输路线（公路、铁路、河流航运线、航空线、管道运输路线等）的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。 最短路问题在实际中还常用于汽车导航系统以及各种应急系统等（110报警、119火警以及120医疗救护系统），这些系统一般要求计算出到出事地