求单源最短路径—Dijkstra算法实验报告.doc
本科学生综合性实验报告项目组长 杨滨 学号 成 员 杨滨 专 业软件工程 班级 12软件 2班 实验项目名称 求单源最短路径Dijkstra算法 指导教师及职称赵晓平 讲师 开课学期 13 至14 学年一学期上课时间 2013 年 9 月 1 日学生实验报告三（综合性实验）学生姓名杨滨学号同组人实验项目求单源最短路径Dijkstra算法必修 选修演示性实验 验证性实验 操作性实验 综合性实验实验地点W101实验仪器台号指导教师赵晓平实验日期及节次2013.12.17(二) 12节2013.12.19(一) 89A节一、实验综述1、实验目的及要求 （1）了解求最优化问题的贪心算法，了解贪心法的基本要素，学会如何使用贪心策略设计算法； （2）了解单源最短路径问题，掌握Dijkstra算法的思想； （3）编写程序，利用Dijkstra算法实现，求任意两点间的单源最短路径。实验题： 给出如右有向图的边权图，求任意两点间的单源最短路径。 实验要求：认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告要求写出操作步骤、结果、问题、解决方法、体会等。2、实验仪器、设备或软件 计算机、VC+6.0、office、相关的操作系统等。二、实验过程（实验步骤、记录、数据、分析）#include<iostream>using namespace std;/*void Graph(int n,bool *inS,int a66,int *d)inS=new booln;inS0=0;for(int i=1;i<n;i+)inSi=1;a=new int*n;for(i=0;i<n;i+)ai=new intn;cout<<"input "<<endl;for(i=0;i<n;i+)for(int j=0;j<n;j+)cin>>aij;d=new intn;for(i=0;i<n;i+)di=a0i;*/int Choose(int 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=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;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<<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<<"input "<<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、分析讨论这个实验稍微复杂些，在实现算法时遇到好多问题，首先要实现距离的算法：图中的数等同于下图： 1 2 3 4 5 6 然后经过Dijkstra算法分析求出最短路径， 1 0 50 10 70 通过这道程序，我明白了：你有了一个算法，2 0 15 10 要通过程序去实现它非常复杂，以后需要勤3 20 0 15 学苦练，加以熟练才能将算法变成程序。4 20 0 35 5 30 0 6 3 0 四、指导教师评语及成绩：成绩： 指导教师签名： 批阅日期：
