算法分析研究与方案实验报告单源最短路径最小生成树.doc

实验报告课程计算机算法设计与分析实验名称单源最短路径、最小生成树学号姓名实验日期:实验三单源最短路径、,掌握原理,运用C++,掌握原理,运用C++(1)设计单源最短路径问题地算法,上机编程实现.(2)设计最小生成树问题地算法,:#include<iostream>usingnamespacestd;#defineMAX999voidgetdata(int**c,intn) {inti,j;intbegin,end,weight; for(i=1;i<=n;i++) {for(j=1;j<=n;j++) {if(i==j) c[i][j]=0; else c[i][j]=MAX; } } do{ cout<<"请输入起点终点权值(-1退出):"; cin>>begin; if(begin==-1)break; cin>>end>>weight; c[begin][end]=weight; }while(begin!=-1);}voidDijkstra(intn,intv,int*dist,int*prev,int**c)b5E2RGbCAP{bools[MAX];inti,j; for(i=1;i<=n;i++) {dist[i]=c[v][i]; //从源点到各点地值 s[i]=false; if(dist[i]==MAX)prev[i]=0; //最大值没有路径 elseprev[i]=v; //前驱为源点 } dist[v]=0;s[v]=true; for(i=1;i<=n;i++) {inttemp=MAX; intu=v; for(j=1;j<=n;j++) if((!s[j])&&(dist[j]<temp)){u=j;temp=dist[j];}//不在集合里,值《temp,选最小值p1EanqFDPw s[u]=true; for(j=1;j<=n;j++){if((!s[j])&&(c[u][j]<MAX)) {intnewdist=dist[u]+c[u][j]; if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}//前驱u记录下来DXDiTa9E3d } }}}voidPrintPath(int*prev,intn,intbegin,intend){int*path=newint[n+1];inti,m=n;boolk=true;path[end]=end; for(i=end-1;i>1;i--) {path[i]=prev[path[i+1]]; //构造路径 m--;} for(i=m;i<=end;i++){ cout<<path[i]<<"->"; //输出路径} cout<<"\b\b"<<""<<endl;}voidmain(){intn,i;intv=1;cout<<"请输入顶点个数:";cin>>n; int*dist=newint[n+1]; int*prev=newint[n+1]; int**c; c=newint*[n+1]; for(i=0;i<=n;i++) {c[i]=newint[n