算法分析与设计实验报告ex3..doc
文本预览下载声明
实验报告
课程 计算机算法设计与分析 实验名称 单源最短路径、最小生成树 学号 姓名 实验日期：
实验三 单源最短路径、最小生成树
一．实验目的
学习单源最短路径问题的简单算法，掌握原理，运用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 // 相关信息字符串的最大长度
显示全部