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

最短路径问题matlab求解详尽版.doc:..最短路径法的说明与实施最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等等。相应地,最短路径问题就成为最快路径问题、最低费用问题等。对于单源点的最短路径问题,一般采用经典的最短路径算法Dijkstra算法,只是不同系统对Dijkstra算法采用了不同的实现方法。但是Dijkstra算法比较繁琐,所以在进行计算的时候我们可以把它转化为Floyd算法。然后再编程实现了该算法丽。Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为屮心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率较低,但作为解决一般最短路问题的方法还是值得我们学习的。最短路径算法的思路介绍Dijkstra算法思想为:设G二(V,E)是一个带权有向图(也可以是无向图,无向图是有向图的特例),把图中顶点集合V分成两组:第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径,就将其加入到集合S中,直到全部顶点都加入到S中,算法就结束了);第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。其步骤主要有"X第一,初始时,S只包含源点,即S={顶点},v的距离为0。U包含除v外的其他顶点,U中顶点u距离为边上的权(若V与U有边)或(若U不是V的出边邻接点)。第二,从U中选取一个距离v最小的顶点k,把k加入S中(该选定的距离就是v至Ijk的最短路径长度)。第三,以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中的顶点二oo,发现A-C二3权值为最短。第二,在S集合中:进入C,此时SKA,C>,此时最短路径A->A二0,A-C二3,以C为中间点,从A-C=3这条最短路径开始找。在U集合中:U=<B,D,E,F>,A-C->B二5(比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-03,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中的顶点二g,发现A-C-D二6权值为最短。第四,在S集合中:进入D,此时S=<A,C,B,D>,此时最短路径A->A=0,A-*O3,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要长),此时至UE权值更改为A->C-E二7,A->C->D-F二9,发现A->C->E=7权值为最短。第五,在S集合中:进入E,此时SNA,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-CfD-F二9要长),此时到F权值更改为A-C-D-F二9,发现A->