算法分析與设计实验报告-单源最短路径最小生成树.docVIP

实验报告 课程 计算机算法设计与分析 实验名称 单源最短路径、最小生成树 学号 姓名 实验日期： 实验三 单源最短路径、最小生成树 一．实验目的 学习单源最短路径问题的简单算法，掌握原理，运用C++编程实现。 学习最小生成树问题的简单算法，掌握原理，运用C++编程实现。 二．实验内容 （1）设计单源最短路径问题的算法，上机编程实现。 （2）设计最小生成树问题的算法，上机编程实现。 三．实验代码 1 . 单源最短路径问题的程序代码如下： #include iostream using namespace std; #define MAX 999 void getdata(int **c,int n) { int i,j; int begin,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退出)：; cinbegin; if(begin==-1) break; cinendweight; c[begin][end]=weight; } while(begin!=-1); } void Dijkstra(int n,int v ,int *dist,int *prev,int **c) { bool s[MAX]; int i,j; for (i=1;i=n;i++) { dist[i]=c[v][i]; //从源点到各点的值 s[i]=false; if(dist[i]==MAX) prev[i]=0; //最大值没有路径 else prev[i]=v; //前驱为源点 } dist[v]=0;s[v]=true; for (i=1;i=n;i++) { int temp=MAX; int u=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)) { int newdist=dist[u]+c[u][j]; if(newdistdist[j]){dist[j]=newdist;prev[j]=u;}//前驱u记录下来 } } } } void PrintPath(int *prev,int n,int begin,int end) { int *path=new int [n+1]; int i,m=n; bool k=true; path[end]=end; for(i=end-1;i1;i--) { path[i]=prev[path[i+1]]; //构造路径 m--; } for (i=m;i=end;i++) { coutpath[i]-; //输出路径 } cout\b\b endl; } void main() { int n,i; int v=1; cout请输入顶点个数：; cinn; int *dist=new int [n+1]; int *prev=new int [n+1]; int **c; c=new int *[n+1]; for (i=0;i=n;i++) { c[i]=new int [n+1]; } getdata(c,n); //获取数据 int begin=1,end; cout请输入所求单源路径的 起点 终点：; cinbeginend; v=begin; Dijkstra(n,v,dist,prev,c); //计算路径 PrintPath(prev,n,begin,end); //输出路径 } 2. 最小生成树问题的程序代码如下： #includemalloc.h #includestdlib.h #includestdio.h #include io.h #include windows.h #include limits.h #define MAX_VERTEX_NUM 20 // 最大顶点个数 #define MAX_NAME 3 // 顶点字符串的最大长度+1 #define MAX_INFO 20 // 相关信息字符串的最大长度