华科算法实验报告.doc

《华科算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程实验报告课程名称：算法设计与分析专业班级：计算机科学与技术13xx班学号：姓名：指导老师：报告日期：2015-11-29计算机科学与技术学院目录一．实验一31．实验题目32．设计思路33．程序源代码44．运行演示7二．实验二81．实验题目82．设计思路83．程序源代码94．运行演示12一．实验一1．实验题目单源最短路径问题：已知一个n结点有向图G=(V,E)和边的权函数c(e)，求由G中某指定结点v0到其它各结点的最短路径。假定边的权值为正。2．设计思路贪心算法流程图如图1：图1生成最短路径算法流程设计总方法：使用贪心算法求解。贪心方法：1)度量标准生成的所有路

2、径长度之和作为度量标准。为了使这一量度达到最小，其单独的每一条路径都必须具有最小长度。2)算法按照路径长度的非降次序生成这些路径。首先，生成一条到最近结点的最短路径，然后，生成一条到第二近结点的最短路径，等等。即只用求出从路径v0开始到G中其他所有结点的最短路径长度。假定G中n个结点被标记上1到n,集合S作为一个数组存放，如果结点i不在S中，则S[i]=0，如果在S中，则S[i]=1，若COST（i,j）是（i,j）的权，则在边（i，j）不在成本邻接矩阵时，就被置某个大数，这里用N表示，当i=j时，COST（i,j）被置以0。3．程序源代码#include

3、o.h>#include#defineN1000voidshortestPaths(intv,int*COST,int*DIST,intn);//最短路径生成函数voidoutput2(int*arr,introw,intcol);//输出成本的邻接矩阵voidoutArray1(int*arr,intn);//输出更新后其它结点到起始结点的路径长度intmain(){intCOST[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

4、,N,N,N,0,10,70},{N,N,N,N,N,0,50},{N,N,N,N,N,N,0}};intDIST[7];intv=0;/*printf("成本邻接矩阵：");output2(&COST[0][0],7,7);*///生成0号结点到1至6号结点的最短路径shortestPaths(v,&COST[0][0],DIST,7);return0;}voidshortestPaths(intv,int*COST,int*DIST,intn){//G是一个n结点有向图，它由其成本邻接矩阵COST[n][n]表示，DIST[j]被置以结点v到//结点j的最短

5、路径长度，这里1<=j<=n;DIST[v]被置成0intS[n];intpre[n];//p[w]记录起始结点到结点w的最短路径中的w前一结点intu,num,i,w;inttv,td=0;//初始化：结点v以外的结点未被选中，并更新路径长度为v到其它结点的初始成本for(i=0;i

6、=DIST[w];tv=w;break;}}for(w++;wDIST[w]){td=DIST[w];tv=w;}}u=tv;S[u]=1;DIST[u]=td;//更新路径for(w=1;w(DIST[u]+*(COST+u*n+w))){DIST[w]=(DIST[u]+*(COST+u*n+w));pre[w]=u;//更新结点w最短路径并记录w结点的上一结点}}}

7、//输出第num次更新后的路径长度printf("第%d次路径:",num);output1(DIST,n);printf("");}//输出路径for(i=1;i