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

本科学生综合性实验报告项目组长杨滨学号_0123707_成员杨滨专业_软件工程班级12软件2班实验项目名称求单源最短路径—Dijkstra算法指导教师及职称_赵晓平讲师___开课学期13至_14学年_一_学期上课时间2013年9月1日学生实验报告三(综合性实验)学生姓名杨滨学号0123707同组人实验项目求单源最短路径——Dijkstra算法√□必修□选修√□演示性实验□验证性实验□操作性实验□(二)(一)89A节一、实验综述1、实验目的及要求(1)了解求最优化问题的贪心算法,了解贪心法的基本要素,学会如何使用贪心策略设计算法;(2)了解单源最短路径问题,掌握Dijkstra算法的思想;(3)编写程序,利用Dijkstra算法实现,求任意两点间的单源最短路径。实验题:给出如右有向图的边权图,求任意两点间的单源最短路径。实验要求:认真完成实验题,能正确运行,提交实验报告并上传程序,实验报告要求写出操作步骤、结果、问题、解决方法、体会等。2、实验仪器、设备或软件计算机、VC++、office、相关的操作系统等。二、实验过程(实验步骤、记录、数据、分析)#include<iostream>usingnamespacestd;/*voidGraph(intn,bool*inS,inta[6][6],int*d){ inS=newbool[n]; inS[0]=0; for(inti=1;i<n;i++) inS[i]=1; a=newint*[n]; for(i=0;i<n;i++) a[i]=newint[n]; cout<<"input"<<endl; for(i=0;i<n;i++) for(intj=0;j<n;j++) cin>>a[i][j]; d=newint[n]; for(i=0;i<n;i++) d[i]=a[0][i];}*/intChoose(intn,int*d,bool*s){ inti,minpos=-1,min=500; for(i=1;i<n;i++) if(d[i]<min&&!s[i]) {min=d[i];minpos=i;} returnminpos;}voidDijkstra(ints,intn,bool*inS,int*d,int*path,inta[6][6]){ intk,i,j; for(i=0;i<n;i++) { inS[i]=false;d[i]=a[s][i]; if(i!=s&&d[i]<500)path[i]=s; elsepath[i]=-1; } inS[s]=true;d[s]=0; for(i=0;i<n-1;i++) { k=Choose(n,d,inS); inS[k]=true; for(j=0;j<n;j++) if(!inS[j]&&d[k]+a[k][j]<d[j]) {d[j]=d[k]+a[k][j];path[j]=k;} }}voidDisplay(ints,intn,inta[6][6],int*d,int*path){intt,m; cout<<"a["<<n<<"]["<<n<<"]:"<<endl; for(inti=0;i<n;i++) {