《最短路径问题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运行图根据程序显示s点到j点的最短路就是27.8公里。在程序中显示所走的路线为path=1 2 3 11，对应点即为先从S点到A点，再从A点到B点，最后由B点到J点。但是由于运用dijkstra编程每次都要修改起始点和终点，所以在大部分情况下效率都不高
