实验1贪心法求解单源最短路径问题

《实验1贪心法求解单源最短路径问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验1・贪心法求解单源最短路径问题实验内容木实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试)。应用贪心策略求解有向带权图的单源最短路径问题。实验目的♦通过本次实验，掌握算法设计与分析的一•般过程，以及每个步骤的基本方法。并应用贪心法求解单源最短路径问题。环境要求对于环境没有特别要求。对于算法实现，可以白由选择C,C++,Java,冥至于其他程序设计语言。实验步步骤1：理解问题，给出问题的描述。步骤2：算法设计，包括策略与数据结构的选择步

2、骤3：描述算法。希望采用源代码以外的形式，如伪代码、流程图等；步骤4：算法的正确性证明。需要这个环节，在理解的基础上对算法的正确性给了证明;步骤5：算法复杂性分析，包括时间复杂性和空间复杂性；步骤6：算法实现与测试。附上代码或以附件的形式提交，同时贴上算法运行结果截图;步骤7：技术上、分析过程中等各种心得休会与备忘，需要言之有物。说明：步骤1・6在“实验结果”一节屮描述，步骤7在“实验总结”一节屮描述。实验结果1•问题描述给定一个有向带全图G=(V,E),其中每条边的权是一个非负实数。另外，给定V中的一个顶

3、点，称为源点。现在要计算源点到所有其他各个顶点的最短路径长度，这里的路径长度是指路径上所有经过边的权值之和。这个问题通常称为单源最短路径问题。2.(l)Dijkstra算法思想按各个结点与源点之间路径长度的非减次序，生成源点到各个结点的最短路径的方法。即先求出长度最短的一条路径，再参照它求出长度次短的一条路径。依此类推，肓到从源点到其它各结点的最短路径全部求出为止。1959年捉出的，但当时并未发表。因为在那个年代，算法基本上不被当做一种科学研究的问题。(2)Dijkstra算法设计集合sAiv-s的划分：假

4、定源点为u。集合s中的结点到源点的最短路径的长度已经确定，集合v-s中所包含的结点到源点的最短路径的长度待定。特殊路径：从源点出发只经过s中的结点到达v-s中的结点的路径。贪心策略：选择特殊路径长度最短的路径，将其相连的v-s-p的结点加入到集合s中。3、描述算法Dijkstra算法的伪代码：DIJKSTRA(G,w,s)INITIALIZE-SINGLE-SOURCE(G,s)S=OQ=G.V//V-S中的结点按特殊路径长度非减排序whileQ工①u=EXTRACT-MIN(Q)S=SU{u)foreac

5、hvEG.AdjLuJRELAX(u,v,w)4、Dijkstra算法的求解步骤：步骤1：设计合适的数据结构。带权邻接矩阵C记录结点Z间的权值，数组dist来记录从源点到其它顶点的最短路径长度，数组P來记录最短路径。U为源点；步骤2：初始化。令集合S={u},对于集合V・S中的所有顶点x,设置dist[x]=C[u][x]o如果顶点x与源点相邻,设置p[x]=u；否则,p[x]=-l；步骤3：贪心选择结点。在集合V-S中依照贪心策略来寻找使得dist[x]具冇最小值的顶点t,t就是集合V-S中距离源点u最近

6、的顶点。步骤4：更新集合S和V・S。将顶点t加入集合S中，同时更新集合V・S；步骤5：判断算法是否结束。如果集合V・S为空，算法结束。否则，转步骤6；步骤6：对相关结点做松弛处理。对集合V-S屮的所有与顶点t和邻的顶点x,如dist[x]>dist[t]+C[t][x],则dist[x]=dist[t]+C[t][x]并设置p[x]=to转步骤3。5、Dijkstra算法的正确性证明-贪心选择性质：采川归纳法。当S={s,p}时，贝IJ除源结点s之外的所有结点屮，结点P到源点s的距离最短。这是显然的。假设当

7、S={s,pl,…,pk}时，即k个结点pl,…,pk到源点s的距离最短。当S={s,pl,…,pk,pk+1}时,很显然结点pk+1到源点s的距离是最短的。需证明：此时结点pl,…,pk到源点s的距离仍然是最短的。用反证法假设当结点pk+1加入到S后，pi结点经由结点pk+1到源点s的距离更短,即d(s,pk+1)+d(pk+l,pi)

8、(logn)；二重循环的执行次数为(n-l)+(n-2)+・・・+l=n(n-l)/2,即时间复朵性为O(n2)。所以，该算法的时间复杂性为0(n2)o空间复杂性：优先队列Q的大小为n・l；所以，该算法的空间复杂性为O(n)。7、算法实现与测试。-口一点接顶邻入入99999923A*SAI./•./•8-▼■""—_BVA.m+Tr0999516102131999092999?09991299011"9为为为为0