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

莁实验报告蒀课程肈计算机算法设计与分析薃实验名称螂单源最短路径、最小生成树膂学号袇蚃姓名膃蚀实验日期:蚆螃薄实验三单源最短路径、,掌握原理,运用C++,掌握原理,运用C++(1)设计单源最短路径问题地算法,(2)设计最小生成树问题地算法,:薁#include<iostream>膆usingnamespacestd;芇#defineMAX999薂voidgetdata(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+1];}莁聿 getdata(c,n); //获取数据莆 intbegin=1,end;螄 cout<<"请输入所求单源路径地起点终点:";螂 cin>>begin>>end;螁 v=begin;荿 Dijkstra(n,v,dist,prev,c); //计算路径袄 PrintPath(prev,n,begin,end); //输出路径膃}:膈#include""羄#include""薄#include""羁#include<>羇#include<>肄#include<>蚁蒈#defineMAX_VERTEX_NUM20 //最大顶点个数蚅#defineMAX_NAME3//顶点字符串地最大长度+1膄#defineMAX_INFO20//相关信息字符串地最大长度+1肁#defineINFINITYINT_MAX //用整型最大值代替∞膀typedefintVRType;螈typedefcharInfoType;芄typedefcharVertexType[MAX_NAME];蒂薈