版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
赋权有向图中心问题计算机<1>班余志萍问题描述:设G=(V,E)是一个赋权有向图，v是G的一个顶点，v的偏心距定义为：Max{w∈V,从w到v的最短路径长度}G中偏心距最小的顶点称为G的中心。试利用Floyd算法设计一个求赋权有向图中心的算法。实验任务对于给定的赋权有向图G,计算图的中心。由文件input.txt给出输入数据。第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边，顶点编号为1,2,…,n。接下来的m行中，每行有3个正整数n,v,w,表示图G的一条边(u,v)及其边权w。将计算出的图的中心及其偏心距输出到文件output.txt。第1行是中心的偏心距，第2行是中心的纺号。输入文件示例Input.txt57124132158244255341453输出文件示例Output.txt232.开辟一个动态数组c[n+1][n+1]，利用Floyd算法算出所有顶点对之间的最短路径则：
c[n+1][n+1]：c[1]c[1]c[1]c[1]c[1]１０４２３６２∞０∞４５３∞∞０１４４∞∞∞０３５∞∞∞∞０3.在比较c[n+1][n+1]中的每一列中的最大值即为该列所对应的顶点的偏心距，开辟一个动态数组max[n+1]，存放每个顶点的偏心距
max[n+1]： 0 4 2 4 64.从max[n+1]中找出偏心距最小的顶点并输出其偏心距及编号核心代码：for(i=1;i<=n;i++)//求出所有顶点对的最短距离 for(j=1;j<=n;j++){ c[i][j]=a[i][j]; } for(i=1;i<=n;i++) c[i][i]=0; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++){ t1=c[i][k]; t2=c[k][j]; t3=c[i][j]; if(t1!=32768&&t2!=32768&&(t3==32768||t1+t2<t3)) c[i][j]=t1+t2; }for(j=1;j<=n;j++)//求所有顶点的偏心距 for(i=1;i<=n;i++) if((c[i][j]>max[j])&&(c[i][j]!=32768)) max[j]=c[i][j]; dis=32768;center=0;//找出最小的偏心距 for(i=1;i<=n;i++) if(max[i]<dis&&max[i]!=0) { dis=max[i]; center=i; } printf
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论