电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

华科算法实验报告VIP免费

华科算法实验报告_第1页
1/13
华科算法实验报告_第2页
2/13
华科算法实验报告_第3页
3/13
课程实验报告课程名称:算法设计与分析专业班级:计算机科学与技术13xx班学号:姓名:指导老师:报告日期:2015-11-29计算机科学与技术学院目录一.实验一.............................................................................................31.实验题目........................................................................................312.设计思路........................................................................................33.程序源代码....................................................................................44.运行演示........................................................................................7二.实验二.............................................................................................81.实验题目........................................................................................82.设计思路........................................................................................83.程序源代码....................................................................................94.运行演示......................................................................................12一.实验一1.实验题目单源最短路径问题:已知一个n结点有向图G=(V,E)和边的权函数c(e),求由G中某指定结点v0到其它各结点的最短路径。假定边的权值为正。2.设计思路贪心算法流程图如图1:2图1生成最短路径算法流程设计总方法:使用贪心算法求解。贪心方法:1)度量标准生成的所有路径长度之和作为度量标准。为了使这一量度达到最小,其单独的每一条路径都必须具有最小长度。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。33.程序源代码#include#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,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("成本邻接矩阵:\n");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的最短路径长度,这里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;iDIST[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结点的上一结点}}}//输出第num次更新后的路径长度printf("\n第%d次路径:",num);output1(DIST,n);printf("\n...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

华科算法实验报告

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部