算法分析与方案实验报告单源最短路径最小生成树.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)芃{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,选最小值衿 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记录下来肆}羃}螈 }莆}膆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];莃蕿//邻接矩阵的数据结构蒈typedefstr