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

最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等等。相应地,最短路径问题就成为最快路径问题、最低费用问题等。对于单源点的最短路径问题,一般采用经典的最短路径算法——Dijkstra算法,只是不同系统对Dijkstra算法采用了不同的实现方法。但是Dijkstra算法比较繁琐,所以在进行计算的时候我们可以把它转化为Floyd算法。然后再编程实现了该算法[23]。Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率较低,但作为解决一般最短路问题的方法还是值得我们学习的。最短路径算法的思路介绍Dijkstra算法思想为:设G=(V,E)是一个带权有向图(也可以是无向图,无向图是有向图的特例),把图中顶点集合V分成两组:第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径,就将其加入到集合S中,直到全部顶点都加入到S中,算法就结束了);第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入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为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。第四,重复步骤第二步和第三步直到所有顶点都包含在S中。,从A到F有多条路线选择,怎样选择可以使运输线路最短,当然在实际问题中权可以认为是费用,效率等因素。用Dijkstra算法可以这样进行,在A、F两地的交通图中的点B、C、D、E分别表示四个地名,点与点之间的连线表示两地之间的公路,边上所赋值代表两地间的长度(单位为公里):,在S集合中:进入A,此时S=<A>,此时最短路径为A→A=0,以A为中间点,从A开始找。在U集合中:U=<B,C,D,E,F>,A→B=6,A→C=3,A→其他U中的顶点=∞,发现A→C=3权值为最短。第二,在S集合中:进入C,此时S=<A,C>,此时最短路径A→A=0,A→C=3,以C为中间点,从A→C=3这条最短路径开始找。在U集合中:U=<B,D,E,F>,A→C→B=5(比A→B=6要短),此时到B权值为A→C→B=5,A→C→D=6,A→C→E=7,A→C→其他U中的顶点=∞,发现A→C→B=5权值为最短。第三,在S集合中:进入B,此时S=<A,C,B>,此时最短路径A→A=0,A→C=3,A→C→B=5,以B为中间点,从A→C→B=5这条最短路径开始找。在U集合中:U=<D,E,F>,A→C→B→D=10(比第二步的A→C→D=6要长),此时到D权值改为A→C→D=6,A→C→B→其他U中的顶点=∞,发现A→C→D=6权值为最短。第四,在S集合中:进入D,此时S=<A,C,B,D>,此时最短路径A→A=0,A→C=3,A→C→B=5,A→C→D=6,以D为中间点,从A→C→D=6这条最短路径开始找。在U集合中,U=<E,F>,A→C→D→E=8(比第二步的A→C→E=7要长),此时到E权值更改为A→C→E=7,A→C→D→F=9,发现A→C→E=7权值为最短。第五,在S集合中:进入E,此时S=<A,C,B,D,E>,此时最短路径为A→A=0,A→C=3,A→C→B=5,A→C→D=6,A→C→E=7,以E为中间点,从A→C→E=7这条最短路径开始找。在U集合中:U=<F>,A→C→E→F=12(比第四步的A→C→D→F=9要长),此时到F权值更改为A→C→D→F=9,发现A→C→D→F=9权值为最短。第六,在S集合中:进入F,此时S=<A,C,B,D,E,F>,此时最短路径为A→A=0,第七,得到最