用matlab实现寻找最短路

用matlab寻找赋权图中的最短路中的应用■=j最1弓1言图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。这些古老的难题，吸引了很多学者的注意。1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出很大的作用。在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条距离最小的路。2最短路2.1最短路的定义(short-pathproblem)对最短路问题的研究早在上个世纪 60年代以前就卓有成效了，其中对赋权图^w^>0)的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的，该算法能够解决两指定点间的最短路，也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法，它能有效地解决含有负权的最短路问题。但在现实生活中，我们所遇到的问题大都不含负权，所以我们在^w^>0)的情况下选择Dijkstra算法。若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管路铺设、线路安装、厂区布局和设备更新等，而且经常被作为一个基本的工具，用于解决其他的做优化问题。定义1：若图G=G(V，E)中个边［气,叩都赋有一个实数w..，则称这样的图G为赋权图，w..称为边［v.,Vj］上的权。定义2:给定一个赋权有向图，即给一个有向图D=(V,A)，对每一个弧3=(%^)，相应地有权w(a)=w„，又给定D中的两个顶点v，气。设P是D中从v到的一条路，定义路P的权是P中所有弧的权之和，记为w(P)。最短路问题就是要在所有从七到气的路中，求一条权最小的路，即求一条从vs到气的路P0，使w(P0)=minw(P)式中对D中所有从v,到vt的路P最小，称*是从%到vt的最短路。2.2最短路问题算法的基本思想及其基本步骤在求解网络图上节点间最短路径的方法中，目前国内外一致公认的比较好的算法有Dijkstra和Floyd算法。这两种算法，网络被抽象为一个图论中定义的有向图或无向图，并利用图的节点邻接矩阵记录点的关联信息。在进行图的遍历搜索最短路径时，以该矩阵为基础不断进行目标值的最小性判别，知道获得最后的优化路径。鉴于课本使用Dijkstra算法，下面用Floyd算法进行计算：设A=(a)n*n为赋权图G=(V,E,F)的矩阵，当Vv^.EE时，%.=F(气，v)，否则，取a=0，a=+8(#；)，d..表示从v.到v.的点的距离，/表示从v到、.的点的最短路中的一个点的编号。 "i V''赋初值。对所有i,j，d广a；，r..=j，k=1，转向②;更新d..，r..，对所有i，j，若史+仪.<d..,则令d.=史+由.，r..=k，转向；jj iRk；j ；ikk；i；终止判判断。若d..<0,则存在一条含有顶点V.的负回路，终止；或者k=n，终止；否则，j另k=k+1，转向②。最短路线可由r；得到。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,j)=D(i,k)+D(k,j);%更新dijR(i,j)=k;%更新rijend;end;endk%显示迭代步数D%显示每步迭代后的路长R%显示每步迭代后的路径pd=0;for(i=1:n)%含有负权if(D(i,j)<0)pd=1;break;end;end%存在一条含有顶点的vi的负回路

if(pd)break;end%存在一条负回路，终止程序end %程序结束下面用一个实际的例子进行一下函数实际运算:例：求解下赋权图中任意两点中的最短路。用matlab函数运行以后，运行结果如下：请输入矩阵的阶n=8请输入赋权图对应的n阶矩阵A=[0281infinfinfinf;206inf1infinfinf;8607512inf;1inf70infinf9inf;inf15inf03inf8;infinf1inf3046;infinf29inf403;infinfinfinf8630]k=1D=0281InfInfInfInf20631InfInfInf8607512Inf1370InfInf9InfInf15Inf03Inf8InfInf1Inf3046InfInf29Inf403InfInfInfInf86301234567812315678123456781134567812345678123456781234567812345678

02813InfInfInf20631InfInfInf8607512Inf13704Inf9Inf315403Inf8InfInf1Inf3046InfInf29Inf403InfInfInfInf86301234267812315678123456781134267822325678123456781234567812345678k=3D=02813910Inf2063178Inf8607512Inf1370489Inf3154037897183036108297303InfInfInfInf8630R=1234233812315338123456781134237822325638333356383334337812345678

02813910Inf2063178Inf8607512Inf1370489Inf3154037897183036108297303InfInfInfInf86301234233812315338123456781134237822325638333356383334337812345678k=5D=0281361011206314898607512131370479123154037864173036108297303119131286301234253512315535123456751134257522325638553556383334337855555678

D=02713691120531479750741271370479123144036864173036972963031197128630R=1264256512615565663466761134257522625668553556386634637855655678k=7D=02713691120531479750741251370479123144036864173036972963031195128630R=1264256512615565663466771134257522625668553556386634637855755678

D=02713691120531479750741251370479123144036864173036972963031195128630R=1264256512615565663466771134257522625668553556386634637855755678注：上例中是用一个无向赋权图，对与有向赋权图只需要把反向的定义为无穷大（在matlab中即用inf代替不能到达的情况），一样可以调用上述函数程序进行运算。3最短路的实际应用最短路问题在交通网络结构的分析，交通运输路线（公路、铁路、河流航运线、航空线、管道运输路线等）的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。最短路问题在实际中还常用于汽车导航系统以及各种应急系统等（110报警、119火警以及120医疗救护系统），这些系统一般要求计算出到出事地点的最佳路线的时间最短。利用最短路还需要实际计算出前方的行驶路线，这就决定了最短路径问题的实现应该是