《单源最短路径贪心算法报告》由会员分享，可在线阅读，更多相关《单源最短路径贪心算法报告（6页珍藏版）》请在金锄头文库上搜索。
1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划单源最短路径贪心算法报告算法分析与设计实验报告第5次实验附录：完整代码#include#include#include#definemaxint1000intc200200=0;voidDijkstra(intn,intv,intdist,intprev)boolsmaxint;for(inti=1;i50)cij=1000;printf(请输入源点：);scanf(%d,&v);intdistn+1,prevn+1;printf(n路径：n);for(inti=1;i；从Vs出发到
2、Vj的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj。若定义一个数组distn，其每个disti分量保存从Vs出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：disti=Mindistk|VkV-S利用公式就可以依次找出下一条最短路径。在程序中c表示带权邻接矩阵，dist表示顶点到源点的最短路径，p记录顶点到源点最短路径的前驱节点，u源点，函数Way是递归的构造出最短路径的次序。五、实验结果程序执行的结果：六、源代码#include#includ
3、eusingnamespacestd;#defineMAX999voidgetdata(int*c,intn)inti,j;intbegin,end,weight;for(i=1;ibegin;if(begin=-1)break;cinendweight;cbeginend=weight;while(begin!=-1);voidDijkstra(intn,intv,int*dist,int*prev,int*c)boolsMAX;inti,j;for(i=1;i1;i-)pathi=prevpathi+1;/构造路径m-;for(i=m;i;/输出路径coutn;int*dist=newin
4、tn+1;int*prev=newintn+1;int*c;c=newint*n+1;for(i=0;ibeginend;v=begin;Dijkstra(n,v,dist,prev,c);/计算路径PrintPath(prev,n,begin,end);/输出路径system(pause);本科学生综合性实验报告项目组长杨滨学号成员杨滨专业软件工程班级12软件2班实验项目名称求单源最短路径Dijkstra算法指导教师及职称赵晓平讲师开课学期13至14学年一学期上课时间XX年9月1日学生实验报告三一、实验综述1、实验目的及要求了解求最优化问题的贪心算法，了解贪心法的基本要素，学会如何使用贪心策
5、略设计算法；了解单源最短路径问题，掌握Dijkstra算法的思想；编写程序，利用Dijkstra算法实现，求任意两点间的单源最短路径。实验题：给出如右有向图的边权图，求任意两点间的单源最短路径。实验要求：认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告要求写出操作步骤、结果、问题、解决方法、体会等。2、实验仪器、设备或软件计算机、VC+、office、相关的操作系统等。二、实验过程#includeusingnamespacestd;/*voidGraph(intn,bool*inS,inta66,int*d)inS=newbooln;inS0=0;for(inti=1;iaij;d
6、=newintn;for(i=0;it;coutn;inS=newbooln;/*a=newint*n;for(i=0;iaij;*/path=newintn;d=newintn;/Graph(n,inS,a,d);ints=0;Dijkstra(s,n,inS,d,path,a);Display(s,n,a,d,path);return0;三、结论1、实验结果2、分析讨论这个实验稍微复杂些，在实现算法时遇到好多问题，首先要实现距离的算法：图中的数等同于下图：然后经过Dijkstra算法分析求出最短路径，10501070通过这道程序，我明白了：你有了一个算法，201510要通过程序去实现它非常复杂，以后需要勤320015学苦练，加以熟练才能将算法变成程序。4200355300630四、指导教师评语及成绩：成绩：指导教师签名：批阅日期：目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水平，并确保其在这个行业的安全感。
