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

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

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

3、d Graph(int n,bool *inS,int a66,int *d) inS=new bool n;in S0=0;for(i nt i=1;i< n;i+)in Si=1;a=new int*n;for(i=0;i< n;i+) ai=new in t n;cout<<"i nput "<<e ndl; for(i=0;i< n;i+) for(i nt j=0;j <n ;j+)cin>>aij;d=new intn; for(i=0;i<n;i+) di=a0i;*/int Choose(in

4、t n,int *d,bool *s)int i,minpos=-1,min=500; for(i=1;i<n;i+) if(di<min && !si) min=di;minpos=i; return minpos;void Dijkstra(int s,int n,bool *inS,int *d,int *path,int a66) int k,i,j; for(i=0;i<n;i+) inSi=false;di=asi; if(i!=s && di<500) pathi=s; else pathi=-1; inSs=true;ds

5、=0; for(i=0;i<n-1;i+) k=Choose(n,d,inS); inSk=true; for(j=0;j<n;j+)if(!inSj && dk+akj<dj) dj=dk+akj;pathj=k; void Display(int s,int n,int a66,int *d,int *path)int t,m;cout<<"a"<<n<<""<<n<<": "<<endl;for(int i=0;i<n

6、;i+)for(int j=0;j<n;j+) cout<<aij<<" "cout<<endl;cout<<" 输入终点 : "cin>>t;cout<<" 距离为 d"<<t<<": "<<dt<<"cout<<" 路径为 : "<<t;while(t!=s)m=patht;cout<<m;t=m;cout<<

7、endl;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,500,500,3,500,0;cout<<"Input n: "cin>>n;inS=new booln;/* a=new int*n;for(i=0;i<n;i+) ai=new intn;cout<<"inpu

8、t "<<endl; for(i=0;i<n;i+) for(int j=0;j<n;j+) cin>>aij;*/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、分析讨论这个实验稍微复杂些，在实现算法时遇到好多问题，首先要实现距离的算法：图中的数等同于下图11:23456然后经过Dijkstra 算法分析求出最短路径,1厂05010OO70OO-1通过这道程序，我明白了：你有了一个算法，2 1OO015OO10