华科算法实验报告.doc

课 程 实 验 报 告 课程名称： 算法设计与分析5-11-29 计算机科学与技术学院 目录 一．实验一 3 1．实验题目 3 2．设计思路 3 3．程序源代码 4 4．运行演示 7 二．实验二 8 1．实验题目 8 2．设计思路 8 3．程序源代码 9 4．运行演示 12 一．实验一 1．实验题目 单源最短路径问题： 已知一个n结点有向图G=(V,E)和边的权函数c(e)，求由G中某指定结点v0到其它各结点的最短路径。假定边的权值为正。 2．设计思路 贪心算法流程图如图1： 图1 生成最短路径算法流程 设计总方法： 使用贪心算法求解。 贪心方法： 1) 度量标准 生成的所有路径长度之和作为标准。为这一量度达到最小，其单独的每一条路径都具有最小长度。 按照路径长度的非降次序生成这些路径。，生成一条到最近结点的短路径然后，生成一条到第二近结点的最短路径，等等。i,j）是（i,j）的权，则在边（i，j）不在成本邻接矩阵时，就被置某个大数，这里用N表示，当i=j时，COST（i,j）被置以0。 3．程序源代码 #include stdio.h #include stdlib.h #define N 1000 void shortestPaths(int v,int *COST,int *DIST,int n);//最短路径生成函数 void output2(int *arr,int row,int col);//输出成本的邻接矩阵 void outArray1(int *arr,int n);//输出更新后其它结点到起始结点的路径长度 int main() { int COST[7][7]={ {0,20,50,30, N, N, N}, {N, 0,25, N, N,70, N}, {N, N, 0,40,25,50, N}, {N, N, N, 0,55, N, N}, {N, N, N, N, 0,10,70}, {N, N, N, N, N, 0,50}, {N, N, N, N, N, N, 0} }; int DIST[7]; int v=0; /* printf(成本邻接矩阵：\n); output2(COST[0][0],7,7); */ //生成0号结点到1至6号结点的最短路径 shortestPaths(v,COST[0][0],DIST,7); return 0; } void shortestPaths(int v,int *COST,int *DIST,int n) {//G是一个n结点有向图，它由其成本邻接矩阵COST[n][n]表示，DIST[j]被置以结点v到 //结点j的最短路径长度，这里1=j=n;DIST[v]被置成0 int S[n]; int pre[n];//p[w]记录起始结点到结点w的最短路径中的w前一结点 int u,num,i,w; int tv,td=0; //初始化：结点v以外的结点未被选中，并更新路径长度为v到其它结点的初始成本 for(i=0;in;i++) { S[i]=0; *(DIST+i)=*(COST+v*n+i); pre[i]=0; } S[v]=1; DIST[v]=0; //更新路径长度 for(num=1;numn;num++) { //选择距离结点 v 最近的结点 w for(w=1;wn;w++) { if(S[w]==0) { td=DIST[w]; tv=w; break; } } for(w++;wn;w++) { if(S[w]==0tdDIST[w]) { td=DIST[w]; tv=w; } } u=tv; S[u]=1; DIST[u]=td; //更新路径