求单源最短路径—Dijkstra算法实验报告.doc

《求单源最短路径—Dijkstra算法实验报告.doc》由会员分享，可在线阅读，更多相关《求单源最短路径—Dijkstra算法实验报告.doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 本科学生综合性实验报告项目组长 杨滨 学号 成 员 杨滨 专 业软件工程 班级 12软件 2班 实验项目名称 求单源最短路径Dijkstra算法 指导教师及职称赵晓平 讲师 开课学期 13 至14 学年一学期上课时间 2013 年 9 月 1 日学生实验报告三（综合性实验）学生姓名杨滨学号同组人实验项目求单源最短路径Dijkstra算法必修 选修演示性实验 验证性实验 操作性实验 综合性实验实验地点W101实验仪器台号指导教师赵晓平实验日期及节次2013.12.17(二) 12节2013.12.19(一) 89A节一、实验综述1、实验目的及要求 （1）了解求最优化问题的贪心算法，了解贪心法的

2、基本要素，学会如何使用贪心策略设计算法； （2）了解单源最短路径问题，掌握Dijkstra算法的思想； （3）编写程序，利用Dijkstra算法实现，求任意两点间的单源最短路径。实验题： 给出如右有向图的边权图，求任意两点间的单源最短路径。 实验要求：认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告要求写出操作步骤、结果、问题、解决方法、体会等。2、实验仪器、设备或软件 计算机、VC+6.0、office、相关的操作系统等。二、实验过程（实验步骤、记录、数据、分析）#includeusing namespace std;/*void Graph(int n,bool *inS,in

3、t a66,int *d)inS=new booln;inS0=0;for(int i=1;in;i+)inSi=1;a=new int*n;for(i=0;in;i+)ai=new intn;coutinput endl;for(i=0;in;i+)for(int j=0;jaij;d=new intn;for(i=0;in;i+)di=a0i;*/int Choose(int n,int *d,bool *s)int i,minpos=-1,min=500;for(i=1;in;i+)if(dimin & !si) min=di;minpos=i; return minpos;void D

4、ijkstra(int s,int n,bool *inS,int *d,int *path,int a66)int k,i,j;for(i=0;in;i+)inSi=false;di=asi;if(i!=s & di500) pathi=s;else pathi=-1;inSs=true;ds=0;for(i=0;in-1;i+)k=Choose(n,d,inS); inSk=true; for(j=0;jn;j+) if(!inSj & dk+akjdj) dj=dk+akj;pathj=k; void Display(int s,int n,int a66,int *d,int *pat

5、h) int t,m;coutann: endl;for(int i=0;in;i+)for(int j=0;jn;j+)coutaij ;coutendl;coutt;cout距离为 dt: dt ;cout路径为: t;while(t!=s)m=patht;coutm;t=m;coutendl;int main()int n,*d,*path;/*a,bool *inS;int a66=0,50,10,500,70,500,500,0,15,500,10,500,20,500,0,15,500,500,500,20,500,0,35,500,500,500,500,30,0,500,500

6、,500,500,3,500,0;coutn;inS=new booln;/*a=new int*n;for(i=0;in;i+)ai=new intn;coutinput endl;for(i=0;in;i+)for(int j=0;jaij;*/path=new intn;d=new intn;/Graph(n,inS,a,d);int s=0;Dijkstra(s,n,inS,d,path,a);Display(s,n,a,d,path);return 0;三、结论1、实验结果2、分析讨论这个实验稍微复杂些，在实现算法时遇到好多问题，首先要实现距离的算法：图中的数等同于下图： 1 2 3 4 5 6 然后经过Dijkstra算法分析求出最短路径，10 501070 通过这道程序，我明白了：你有了一个算法，20 15 10 要通过程序去实现它非常复杂，以后需要勤3200 15 学苦练，加以熟练才能将算法变成程序。420 0 35 530 0 63 0 四、指导教师评语及成绩：成绩： 指导教师签名： 批阅日期：