《实验1.-贪心法求解单源最短路径问题》由会员分享，可在线阅读，更多相关《实验1.-贪心法求解单源最短路径问题（6页珍藏版）》请在金锄头文库上搜索。
1、实验1 .贪心法求解单源最短路径问题实验内容本实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法设计、算法描述、算法 正确性证明、算法分析、算法实现与测试)。应用贪心策略求解有向带权图的单源最短路径问题。实验目的通过本次实验，掌握算法设计与分析的一般过程，以及每个步骤的基本方法。并应用贪心 法求解单源最短路径问题。环境要求对于环境没有特别要求。对于算法实现,可以自由选择 C, C+, Java ，甚至于其他程序 设计语言。实验步骤步骤1:理解问题，给出问题的描述。步骤2 :算法设计，包括策略与数据结构的选择步骤3 :描述算法。希望采用源代码以外的形式，如伪代码、流程图等；步骤4:算
2、法的正确性证明。需要这个环节，在理解的基础上对算法的正确性给予证明；步骤5 ：算法复杂性分析，包括时间复杂性和空间复杂性；步骤6:算法实现与测试。附上代码或以附件的形式提交，同时贴上算法运行结果截图步骤7 ：技术上、分析过程中等各种心得体会与备忘，需要言之有物。说明：步骤1-6在“实验结果” 一节中描述，步骤7在“实验总结” 一节中描述。实验结果1 .问题描述给定一个有向带全图G= (V , E),其中每条边的权是一个非负实数。另外，给定V中的一个顶 点，称为源点。现在要计算源点到所有其他各个顶点的最短路径长度，这里的路径长度是指路径 上所有经过边的权值之和。这个问题通常称为单源最短路径问题。
3、2 .( 1)Dijkstra 算法思想按各个结点与源点之间路径长度的非减次序，生成源点到各个结点的最短路径的方法。即先求出长度最短的一条路径，再参照它求出长度次短的一条路径。依此类推，直到从源点到其 它各结点的最短路径全部求出为止。1959年提出的，但当时并未发表。因为在那个年代，算法基本上不被当做一种科学研究的问题。(2)Dijkstra算法设计集合S与V-S的划分：假定源点为u。集合S中的结点到源点的最短路径的长度已经确定，集合V-S中所包含的结点到源点的最短路径的长度待定。特殊路径：从源点出发只经过S中的结点到达V-S中的结点的路径。贪心策略：选择特殊路径长度最短的路径，将其相连的V-
4、S中的结点加入到集合S中。3、描述算法Dijkstra算法的伪代码：DIJKSTRA。w, s)INITIALIZE-SINGLE-SOURCE(G , s)sgQ = G.V /V-S中的结点按特殊路径长度非减排序while Q 工Q)u = EXTRACT-MIN(Q)S = S U ufor each v G.AdjuRELAX(u, v, w)4、Dijkstra算法的求解步骤：步骤1设计合适的数据结构。带权邻接矩阵c记录结点之间的权值，数组dist来记录从源点到其它顶点的最短路径长度，数组 P来记录最短路径。u为源点；步骤2 ：初始化。令集合S=u，对于集合V-S中的所有顶点x，设置
5、distx=Cux o如果顶点x与 源点相邻，设置px=u ；否则，px=-1 ；步骤3：贪心选择结点。在集合V-S中依照贪心策略来寻找使得diSt冈具有最小值的顶点t,t就是集合V-S中距离源点u最近的顶点。步骤4 ：更新集合S和V-S。将顶点t加入集合S中，同时更新集合V-S;步骤5 ：判断算法是否结束。如果集合V-S为空，算法结束。否则，转步骤6 ；步骤6 :对相关结点做松弛处理。对集合V-S中的所有与顶点t相邻的顶点x，如distxdistt+Ctx 则 distx=distt+Ctx并设置 p冈转步骤 3。5、Dijkstra算法的正确性证明-贪心选择性质：采用归纳法。当S=s, p
6、时，则除源结点s之外的所有结点中，结点p到源点s的距离最短。 这是显然的。假设当S=s,p1,pk时，即k个结点p1,pk到源点s的距离最短。当S=s, p1,-,pk, pk+1时，很 显然结点pk+1到源点s的距离是最短的。需证明：此时结点p1,pk到源点s的距离仍然是最短 的。用反证法假设当结点pk+1加入到S后，pi结点经由结点pk+1到源点s的距离更短，即d(s, pk+1) + d(pk+1, pi) d(s, pi)，有 d(s, pk+1) Q4I,H2 2 9 Di 王212 3 4 v 9 9 人 V72K3R 1 79 y 0 1 98242399占舌若点returned
7、 0 sxocut ion t lrc - 1?. wll cr实验总结Dijkstra算法采用贪心策略，按各个顶点与源点之间路径长度递增的次序， 生成源点到各 个顶点的最短路径方法。先求出长度最短的一条路径，在参照它求出长度次短的一条路径，以此类 推，直到从源点到其他各个顶点的最短路径全部求出。在构造带权邻接矩阵时候，二维数组在dijkstra算法里采用指针传递参数，结果求得的最短路径为0x652555等等，因为算法按照课本编写所以觉得没有错，就在输出部分困扰了很久，这样 告诉我们学习不能生搬硬套，出问题不可怕，仔细分析问题来源并解决才是最重要的。在定义无穷大整数时，程序里是999，输入矩阵
8、时变成10000,结果出来很大的数没有规律。在设置循环变量时，从0到n导致输入数组的时候出错，又写了输出语句还是弄不明白，小小的一个bug浪费了大量的时间，现在要好好的弥补编程知识。利用经典的算法知识 可以解决现实生活中的许多问题，利用程序实现充满乐趣和挑战。Dijkstra算法代码:#include using namespace std; const int intmax=999;void Dijkstra(int n,int u,int* distjnt* p,int *&c)bool sn;for(int i=1 ;i=n;i+)disti=cui;si=false;if(disti=
9、intmax)Pi=-1 ；elsePi=u；)dist u=0;su=true;for(int i=1 ;iv=n;i+)int temp=intmax;int t=u;for(intj=1;j=n;j+)if(!sj)&(distjtemp)(t=j；temp=disti;if(t=u)break;st=true;for(j=1；j=n;j+)if(!sO)&(ctO(distt+ctO)(distO=distt+ctO；P0=t；) )int main()(cout输入顶点个数：“；cinn;int* dist=new intn+1;int* p=new intn+1; int* c=new int*n+1; for(int i=O;in;i+)(ci=new intn+1;)cout输入邻接矩阵:endl; for(int i=0;in;i+) (for(int j=O;jiH 路径长度:,distiendl;for(int i=1 ;ivn;i+) (coutvv” 顶点 vvivv” 的前驱顶点为：vvpivvendl；)return 0;/*0 8 32 999 999120 16 15 999999 29 0 999 13999 21 999 0 7999 999 27 19 0 7
