最短路径问题matlab求解详尽版

《最短路径问题matlab求解详尽版》由会员分享，可在线阅读，更多相关《最短路径问题matlab求解详尽版（16页珍藏版）》请在装配图网上搜索。

1、 最短路径法的说明与实施最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其它的度量，如时间、费用、线路容量等等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。对于单源点的最短路径问题，一般采用经典的最短路径算法Dijkstra算法，只是不同系统对Dijkstra算法采用了不同的实现方法。但是Dijkstra算法比较繁琐，所以在进行计算的时候我们可以把它转化为Floyd算法。然后再编程实现了该算法23。 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径

2、。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率较低，但作为解决一般最短路问题的方法还是值得我们学习的。最短路径算法的思路介绍Dijkstra 算法思想为：设G=（V，E）是一个带权有向图（也可以是无向图，无向图是有向图的特例）， 把图中顶点集合V分成两组：第一组为已求出最短路径的顶点集合（用S 表示，初始时S 中只有一个源点，以后每求得一条最短路径，就将其加入到集合S 中，直到全部顶点都加入到S 中，算法就结束了）；第二组为其余未确定最短路径的顶点集合（ 用U 表示）， 按最短路径长度的递增次序依次把

3、第二组的顶点加入S 中。在加入的过程中，总保持从源点v 到S 中各顶点的最短路径长度不大于从源点v 到U 中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S 中的顶点的距离就是从v 到此顶点的最短路径长度，U中的顶点的距离，是从v 到此顶点只包括S 中的顶点为中间顶点的当前最短路径长度。其步骤主要有11：第一，初始时，S 只包含源点，即S顶点，v 的距离为0。U 包含除v 外的其他顶点，U 中顶点u 距离为边上的权（若v 与u 有边）或（若u 不是v 的出边邻接点）。第二，从U 中选取一个距离v 最小的顶点k，把k 加入S 中（该选定的距离就是v 到k 的最短路径长度）。第三，以k 为新

4、考虑的中间点，修改U 中各顶点的距离； 若从源点v 到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u 的距离值，修改后的距离值的顶点k 的距离加上边上的权。第四，重复步骤第二步和第三步直到所有顶点都包含在S 中。3.1.2 最短路径算法的实施步骤假如某企业要将一批产品由A 地运往F地，从A到F有多条路线选择，怎样选择可以使运输线路最短，当然在实际问题中权可以认为是费用，效率等因素。用Dijkstra 算法可以这样进行，在A、F 两地的交通图中的点B、C、D、E 分别表示四个地名，点与点之间的连线表示两地之间的公路，边上所赋值代表两地间的长度（单位为公里）如图3.1所示：5

5、3ABCDFE6234235 图3.1 A到F点的交通模型图第一，在S 集合中：进入A，此时S=，此时最短路径为AA=0，以A 为中间点， 从A 开始找。在U 集合中：U=，AB=6，AC=3，A其他U 中的顶点=，发现AC=3 权值为最短。第二，在S 集合中：进入C，此时S=，此时最短路径AA=0，AC=3，以C 为中间点，从AC=3 这条最短路径开始找。在U 集合中：U=，ACB=5（比AB=6 要短），此时到B权值为ACB=5，ACD=6，ACE=7，AC其他U 中的顶点=，发现ACB=5 权值为最短。第三，在S 集合中：进入B，此时S=，此时最短路径AA=0，AC=3，ACB=5， 以

6、B 为中间点， 从ACB=5 这条最短路径开始找。在U 集合中：U=，ACBD=10（比第二步的ACD=6 要长），此时到D权值改为ACD=6，ACB其他U中的顶点=， 发现ACD=6 权值为最短。第四，在S 集合中：进入D，此时S=，此时最短路径AA=0，AC=3，ACB=5，ACD=6，以D 为中间点，从ACD=6 这条最短路径开始找。在U 集合中，U=，ACDE=8 （ 比第二步的ACE=7 要长），此时到E权值更改为ACE=7，ACDF=9，发现ACE=7 权值为最短。第五，在S 集合中：进入E，此时S=，此时最短路径为AA=0，AC=3，ACB=5，ACD=6，ACE=7，以E 为中

7、间点，从ACE=7 这条最短路径开始找。在U 集合中：U=，ACEF=12 （比第四步的ACDF=9 要长），此时到F 权值更改为ACDF=9，发现ACDF=9 权值为最短。第六，在S 集合中：进入F，此时S=， 此时最短路径为AA=0，第七，得到最短路径。从第六步可知，从A 到F 的最短路径为9 公里，A 到B的最短路径为ACB=5，A 到C 是最短路径为AC=3，A 到D 的最短路径为ACD=6，A 到E 的最短路径为ACE=7，所以A 到F 的最短路径为ACDF=9。Dijkstra算法提供了从网络图中某一点到其他点的最短距离。但实际问题中往往要求网络中任意两点之间的最短路距离。如果仍然

8、采用Dijkstra算法对各点分别计算，就显得很麻烦。所以就可以使用网络各点之间的矩阵计算法，即Floyd算法。Floyd算法的基本是：从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，.，n(n是城市的数目)，在检查d(i,j)与d(i,k)+d(k,j)的值；在此d(i,k)与d(k,j)分别是目前为止所知道的i到k与k到j的最短距离。因此d(i,k)+d(k,j)就是i到j经过k的最短距离。所以，若有d(i,j)d(i,k)+d(k,j)，就表示从i出

9、发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(i,j)重写为d(i,k)+d(k,j)，每当一个k查完了，d(i,j)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(i,j)里面存放的就是i到j之间的最短距离了7。对于上面的问题，只要能列出它的距离的邻接矩阵，如表3.1所示。便能用floyd法进行计算了。南京市区华润苏果超市间的邻接距离，如 表4.1所示表4.1 相邻各点的距离起点SABJIGF终点ABJIHFE距离4.512.610.73.23.12.59.8起点ECBSSS终点DDCCDE距离5.14.35.112.412.713.2 由于数据比较复杂，

10、用普通的计算很困难，所以我们可以用MATLAB软件来编程求解。MATLAB是一款由美国The MathWorks公司出品的商业数学软件。M算法思路：采用标号作业法,每次迭代产生一个永久标号, 从而生长一颗以V0为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径。当然此问题也需要网络各点的邻接矩阵。如图.所示：图.网络各点的邻接矩阵图接下来可以得到Dijkstra法的MATLAB语言M程序function min,path=dijkstra(w,start,terminal)n=size(w,1); label(start)=0; f(start)=start;for i=1:n

11、if i=start label(i)=inf;end, ends(1)=start; u=start;while length(s)(label(u)+w(u,v) label(v)=(label(u)+w(u,v); f(v)=u; end, end, end v1=0; k=inf; for i=1:n ins=0; for j=1:length(s) if i=s(j) ins=1; end, end if ins=0 v=i; if klabel(v) k=label(v); v1=v; end, end, end s(length(s)+1)=v1; u=v1;endmin=lab

12、el(terminal); path(1)=terminal;i=1; while path(i)=start path(i+1)=f(path(i); i=i+1 ;end path(i)=start;L=length(path);path=path(L:-1:1);脚本程序weight=04.5inf12.4 12.7 13.2 inf inf inf inf inf;4.5012.6infinfinfinfinfinfinfinf;inf12.605.1infinfinfinfinfinf10.7;12.4inf5.104.3infinfinfinfinfinf;12.7infinf00

13、5.2infinfinfinfinf;13.2infinf4.35.209.8infinfinfinf;infinfinfinfinf9.802.5infinfinf;infinfinfinfinfinf2.50infinfinf;infinfinfinfinfinfinfinf0 3.1inf;infinfinfinfinfinfinfinf 3.1 03.2;infinf10.7infinfinfinfinfinf3.20 ;dis, path=dijkstra(weight, 1, 11)图4.4所示即Dijkstra法的MATLAB运行图：图4.4Dijkstra法的MATLAB运行图

14、根据程序显示s点到j点的最短路就是27.8公里。在程序中显示所走的路线为path=1 2 3 11，对应点即为先从S点到A点，再从A点到B点，最后由B点到J点。但是由于运用dijkstra编程每次都要修改起始点和终点，所以在大部分情况下效率都不高。由于dijkstra算法较为复杂，所以可用Floyd算法用于求最短路径。Floyd算法思路本质很简单，即用三个for循环的嵌套，代码思路如下：for ( int i = 0; i 节点个数; +i )for ( int j = 0; j 节点个数; +j )for ( int k = 0; k 节点个数; +k )if ( Disik + Diskj

15、 Disij )/ 找到更短路径Disij = Disik + Diskj;但是这里我们要注意循环的嵌套顺序，如果把检查所有节点X放在最内层，那么结果将是不正确的，因为这样便过早的把i到j的最短路径确定下来了，所以正确的应该是这样的： for ( k = 0; k 节点个数; +k )for ( i = 0; i 节点个数; +i )for ( j = 0; j 节点个数; +j )if ( Disik + Diskj .-P-B。这样一来，假设我们要找A-B的最短路径，那么就依次查找，假设Path(AB)的值为P，那么接着查找Path(AP)，假设Path(AP)的值为L，那么接着查找Pat

16、h(AL)，假设Path(AL)的值为A，则查找结束，最短路径为A-L-P-B。那么，如何填充Path的值呢？很简单，当我们发现Dis(AX) + Dis(XB) .-X-.-B，而此时，Path(XB)的值是已知的，所以，Path(AB) = Path(XB)。Floyd算法直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1), D(2), , D(n), D(n)是图的距离矩阵, 同时引入一个后继点矩阵记录两点间的最短路径。d(i,j) : i到j的距离; path(i,j): i到j的路径上i的后继点;输入带权邻接矩阵a(i,j)。赋初值，对所有i,j, d(i,j)

17、a(i,j) , path(i,j)j,k=l。然后更新d(i,j) , path(i,j)对所有i,j,若d(i,k)+d(k,j)d(i,j)则d(i,j)=d(i,k)+d(k,j) , path(i,j)path(i,k) , k =k+1。重复上述步骤直到k=n+1。 接下来就是代入具体的数据了，这里使用图以及邻接矩阵。此问题的邻接矩阵。如表4.2所示： 表4.2 超市间距离的邻接矩阵收发点SABCDEFGHIJS04.512.412.713.2A4.5012.6B12.605.110.7C12.45.104.3D12.7005.2E13.24.35.209.8F9.802.5G2.

18、50H03.1I3.103.2J10.73.20此问题的MATLAB代码如下1、调用M程序的代码function D,path,min1,path1=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j;end, end, endfor 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); path(i,j)=path(i,k);end, end, end,en

19、dif nargin=3 min1=D(start,terminal); m(1)=start; i=1; path1= ; while path(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m;end 2、脚本程序的代码建立脚本文件如下：a=0 4.5 inf 12.4 12.7 13.2 inf inf inf inf inf;4.5012.6infinfinfinfinfinfinfinf;inf12.605.1infinfinfinfinfinf10

20、.7;12.4inf5.104.3infinfinfinfinfinf;12.7infinf005.2infinfinfinfinf;13.2infinf4.35.209.8infinfinfinf;infinfinfinf inf 9.802.5 infinfinf;infinfinfinfinfinf2.5 0 infinfinf;infinfinfinfinfinfinfinf 0 3.1 inf ;infinfinfinfinfinfinfinf 3.1 0 3.2;infinf10.7 inf inf inf inf infinf 3.2 0;D, path=floyd(a)Floy

21、d算法程序的需要注意的问题：1. D, path=floyd(a), 返回矩阵D, path 。其中a是所求图的带权邻接矩阵，D(i,j)表示i到j的最短距离; path(i,j)表示i与j之间的最短路径上顶点i的后继点。2. D, path, min1, path1= floyd(a,i,j) 返回矩阵D, path; 并返回i与j之间的最短距离min1和最短路径path1。MATLAB运行过程如下所示。图4.5所示是网络各点间最短距离矩阵图；图4.6网络各点间最短路线的数组矩阵图；图4.7是程序的运行结果。图4.5 网络各点间最短距离矩阵图图4.6 网络各点间最短路线的数组矩阵图 图4.7

22、 Floyd法MATLAB程序运行结果根据结果可以很快的知道各点到各个点之间的最短路径，S，A，B，CJ对应1到11这11个网点。找到S点到J点的最短路，就是从path矩阵寻找。S到J，即为1到11，首先找到矩阵中点（1，11）为数字2。再从2出发，找到点（2，11）数字为3。再从3出发，找到点（3，11）为数字11。所以最优路线即为从1-2-3-11， 所走的路线为S到A，A到B，B到J。 经过最短路径法的计算，可以发现，车辆路线规划是十分重要的。它可以从理论上找到数学意义上的最短运输路线，比驾驶员按照经验选择路线要合理许多。所以基于最短路径法的车辆路线的对节省配送成本，本提高配送效率，减少配送时间等方面都有重要的意义。当然，在实际的配送运输中，由于没有那么多的约束条件，而且交通状况一直在改变，所以还要根据时间情况进行灵活调整