《图算法及其在通信网中的应用》Dijkstra算法和Dial算法的比较

《《图算法及其在通信网中的应用》Dijkstra算法和Dial算法的比较》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Dijkstra算法和Dial算法的比较李昂2010012010005何庆强2010012010025辜义睿2B辅导老师：王晟、朱永丽—、目录11122Dijkstra算法和Dial算法的比较三、关键词四、问题描述一、目录五、求解思路及方法21.Dijkstra算法及伪码实现22.Dial算法3六、实验设计31.用Dijkstra算法实现（d（i）代表到节点1的距离）42.用Dial算法实现4七、实验结果4八、性能分析41.正确度分析42.复杂度分析5九、结论5十、实验改进方向及应用5十一、附录（只写出主要函数）61.CP

2、ath类62.DijksiraAlg函数73.Update函数84.运行结果8二、弓丨舌在FI常生活中，我们如果需要常常往返A地区和B地区之间，我们最希槊知道的可能是从A地区到B地区间的众多路径中，哪一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（市结点和路径组成的）中两结点之间的最短路径。Dijkstra（迪杰斯特拉）算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为屮心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,

3、一般的表述通常冇两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式。注意该算法要求图中不存在负权边。Dijkstra算法是以起始点为中心向外层层扩展,直到扩展到终点为止,它能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dial算法是Dijkstra算法的变体，采用最短路径搜索技术确定被选择的路径，降低了Dijkstra程序里FindMin函数的复杂度，从而达到加速的目的,提高了算法的效率。三、关键词最短路径，Dijkstra算法，Dial算法，搜索，加速四、问题描述给定有向加权图G(

4、V,E),给定源点/起始点s,求从s出发到V屮其它所有顶点的权重最小的路径。五、求解思路及方法1.Dijkstra算法及伪码实现设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合(用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将加入到集合S屮，直到全部顶点都加入到S屮，算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示)，按最短路径长度的递增次序依次把第二组的顶点加入S^o在加入的过程屮，总保持从源点v到S屮各顶点的最短路径长度不大于从源点v到U中任何顶点

5、的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U屮的顶点的距离，是从v到此顶点只包括S屮的顶点为屮间顶点的当前最短路径t度。①DijkstraAlg(G(V,E),s)FORallvertexjinVDOd(j)=oo;p(j)=NULL;S={s};d(s)=0;p(s)=NULL;Update(s);WHILESVDOi二FindMin();S=SU⑴；Update(i);ENDWHILE②FindMin()FindvertexvinV-Swhichhasminimumd(

6、v);RETURNv;©Update(i)FOReachedgeeincidenttoiDOIFc.weight+d(i)

7、一次找到最小的那个桶开始查找，直到碰到第一个非空的桶为止。桶代表各点到源点的距离，由小到大排列，一个桶里面可以装多个顶点，即这些点到源点的距离相同。更新时，将指向桶的指针依次往后找，而不需耍从头开始，节省了查找的时间，提高了算法效率。六、实验设计根据下面的图求1到6的最短路径1•用Dijkstra算法实现（d（i）代表到节点1的距离）1d(2)d(3)d(4)d(5)d(6)122412323123423612345236412345623646实验程序及结果见附录2.用Dial算法实现引入若干个桶，桶的编号代表路径距离，

8、从小到大由左到右排列。此例子理论上应该引入0〜24的25个桶，在此，为了方便,仅列出0~6的7个桶。通过从最左端的桶开始月•向右扫描直到找到非空桶，来寻找最小值。更新距离更小时，将节点尽量往左边的桶中放。按如下步骤：1—将节点1放入桶0；12—将节点2放入桶2,3放入桶4；123—将节点3从桶4移到桶3