最短路径问题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地,从A到F有多条路线选择,怎样选择可以使运输线路最短,当然在实际问题中权可以认为是费用,效率等因素。用Dijkstra 算法可以这样进行,在A、F 两地的交通图中的点B、C、D、E 分别表示四个地名,点与点之间的连线表示两地之间的公路,边上所赋值代表两地间的长度(单位为公里):
5
3
A
B
C
D
F
E
6
2
3
4
2
3
5
A到F点的交通模型图
第一,在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→