求单源最短路径—dijkstra算法实验报告

《求单源最短路径—dijkstra算法实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、y西財铨火聲本科学生综合性实验报告项目组长杨滨学号0123707杨滨专业软件工程班级12软件2班实验项目名称求单源最短路径一Dijkstra算法指导教师及职称赵晓平讲师开课学期13至14学年一学期上课时间2013年9一、实验综述学生实验报告三(综合性实验)学生姓名杨滨学号0123707同组人实验项目求单源摄短路径Dijkstra算法0必修□选修□演示性实验□验证性实验□操作性实验□综合性实验实验地点W101实验仪器台号指导教师赵晓平实验日期及节次2013.12.17(二)12节2013.12.1

2、9(—)89A节1、实验目的及要求(1)了解求最优化问题的贪心算法，了解贪心法的基本要素，学会如何使用贪心策略设计算法；(2)了解单源最短路径问题，掌握Dijkstra算法的思想；(3)编写程序，利用Dijkstra算法实现，求任意两点间的单源最短路径。实验题：给出如右有向阁的边权阁,求任意两点间的单源最短路径。实验要求：认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告耍求写出操作步骤、结果、问题、解决方法、体会等。2、实验仪器、设备或软件计算机、VC++6.0、office、相关的

3、操作系统等。二、实验过程(实验步骤、记录、数#includeusingnamespacestd;/*voidGraph(intn，bool*inS，inta[6][6]，int*d){inS=newbool[n];inS[0]=0;for(inti=l;i

4、+)d=newint[nj;for(i=0;i

5、){inS[i]=false;d[i]=a[s][i];if(i!=s&&d[i]<500)path[i]=s;elsepath[i]=-l;}inS[s]=true;d[s]=O;for(i=0;i

6、j]&&d[k]+a[k]

7、j]

8、j]){d

9、j]=d[k]+a[k][j];path

10、j]=k;}}voidDisplay(ints，intn，inta[6J[6J,

11、int*d,int*path){intt,m;cout<<”a[,,<

12、h;//**a，bool*inS;inta[6][6]={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,500,500,3,500,0}:cout«"Inputn:cin»n;inS=newbool[n];/*a=newint*[n];for(i=0;i

13、r(i=0;i