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

求单源最短路径—DIJKSTRA算法实验报告.docy西財铨火聲本科学生综合性实验报告项目组长杨滨学号0123707杨滨专业软件工程班级12软件2班实验项目名称求单源最短路径一Dijkstra算法指导教师及职称赵晓平讲师 开课学期 13至14学年一学期上课时间 2013年9一、实验综述学生实验报告三(综合性实验)学生姓名杨滨 学号 0123707同组人实验项目求单源摄短路径 Dijkstra算法0必修□选修□演示性实验□验证性实验□操作性实验□(二)(—)89A节1、 实验目的及要求了解求最优化问题的贪心算法,了解贪心法的基本要素,学会如何使用贪心策略设计算法;了解单源最短路径问题,掌握Dijkstra算法的思想;编写程序,利用Dijkstra算法实现,求任意两点间的单源最短路径。实验题:给出如右有向阁的边权阁,求任意两点间的单源最短路径。实验要求:认真完成实验题,能正确运行,提交实验报告并上传程序,实验报告耍求写出操作步骤、结果、问题、解决方法、体会等。2、 实验仪器、设备或软件计算机、VC++、office、相关的操作系统等。二、实验过程(实验步骤、记录、数#include<iostream>usingnamespacestd;/*voidGraph(intn,bool*inS,inta[6][6],int*d){inS=newbool[n];inS[0]=0;for(inti=l;i<n;i++)inS[i]=l;a=newint*[n];for(i=0;i<n;i++)a[i]=newint[n];cout«"input'*«endl;for(i=0;i<n;i++)for(intj=O;j<n;j++)d=newint[nj;for(i=0;i<n;i++)d[i]=a[O][i];}*/intChoose(intn,int*d,bool*s){inti,minpos=-l,min=500;for(i=l;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]=-l;}inS[s]=true;d[s]=O;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[6J[6J,int*d,int*path){intt,m;cout<<”a[,,<<n«,’][n<<n<<M]:"«endl;for(inti=0;i<n;i++){for(intj=O;j<n;j++)cout«a[i]U]«”’’;cout«endl;}cout«”输入终点:";cin»t;cout«"