首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图G以邻接矩阵的方式存储,G[i][j]中存放的是从结点i出发到结点j的边权,G[i][j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
设有向无环图G以邻接矩阵的方式存储,G[i][j]中存放的是从结点i出发到结点j的边权,G[i][j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
admin
2017-04-28
80
问题
设有向无环图G以邻接矩阵的方式存储,G
[j]中存放的是从结点i出发到结点j的边权,G
[j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。
根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
选项
答案
算法实现如下: int floyd (Graph G) { //构造一个新图 int dist[n](nl; //n是已经定义的常量,代表图中顶点的个数 for (int i=0; i<G.VerticeNum();i++) { for (int j=0;j <G.VerticeNum();j++) { dist[i][j]=—G.weight <i,j); //初始化新图的边权 } } //弗洛伊德算法 for (int k=0; k<G.G.VerticeNum();k++) { for (int i=0; i<G.G.VerticeNum(); i++) for (int j=0;j <G.G.VerticeNum(),j++) if (dist[i][j]>dist [i][kl+distfk][j]) dist [i] [j]=dist [i][k]+dist[k][j]; } //遍历新图,找出最大路径长度 int max=0; for (int i=0; i<G.VerticeNum();i++) for (int j=0;j <G.VerticeNum();j++) int floyd (Graph G) { //构造一个新图 int dist[n](nl; //n是已经定义的常量,代表图中顶点的个数 for (int i=0; i<G.VerticeNum();i++) { for (int j=0;j <G.VerticeNum();j++) { Dist[i][j]=—G.weight <i,j); //初始化新图的边权 } } //弗洛伊德算法 for (int k=0; k<G.G.VerticeNum();k++) { for (int i=0; i<G.G.VerticeNum(); i++) for (int ;=0;j <G.G.VerticeNum(),j++) if (dist[i][j]>dist [i][kl+distfk][j]) dist [i] [j]=dist [i][k]+dist[k][j]; } //遍历新图,找出最大路径长度 int max=0; for (int i=0; i<G.VerticeNum();i++) for (int j=0;j <G.VerticeNum();j++) if(max<—dist[i][j]) max<—dist[i][j]; return max; }
解析
转载请注明原文地址:https://kaotiyun.com/show/2WRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
()是一部上起传说中的黄帝,下迄汉武帝时期的中国通史,是中国历史上第一部内容完整、结构周密的历史著作。
夏王朝建立后,将其领土划分为九州,派九牧进行治理,在九州范围内根据土地的肥沃程度缴纳贡赋,称为()。
提出电磁感应定律的是物理学家()。
二战以来,资本主义经济在发展中出现了许多新问题,这主要表现在()
1942年太平洋战争爆发后,日本先后夺取了焦作、开滦等煤矿,华北沦陷区每年向日本输送的原煤达800万吨。这说明日本在沦陷区进行经济掠夺的直接目的是()。
中古时代实行索贡巡行赋税征收方式的国家是()。
以下不属于国民党控制金融的“四行”的是()。
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
清初,著名学者()在抗清活动失败后东渡日本,讲学授徒,培养了大批学者,传播了中国文化。
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
随机试题
测定凡士林或其他类似物质的熔点,中国药典采用第几法()
浸出物测定用的供试品须粉碎,使能通过
市场预测是市场调查内容在时间上的延伸。投资项目市场预测的内容侧重在______。
会计电算化方式下处理流程与手工方式没有区别。()
证券公司、证券投资咨询机构向客户提供证券投资顾问服务,应当了解的内容不包括()。
位于市区的某汽车制造厂为增值税一般纳税人,主要生产A型小轿车,2019年10月发生以下业务:(1)进口小轿车发动机一批,国外买价折合人民币480万元,运抵我国入关地前支付的运费折合人民币10万元、保险费折合人民币8万元;人关后运抵企业所在地,国内运输企业
树木枝干和许多植物的茎秆通常含有大量难以分解的木质素,因此利用它们来提炼生物燃料的效率要大打折扣。目前,人们发现了一种名为红球菌的细菌,它具有分解木头和其他植物中木质素的能力,因此,人们认为可以将红球菌广泛用于以往大都废弃的茎秆,从而大大提高生物燃料的利用
在宋朝,《洗冤录》是中国乃至世界最早的()
DothefollowingstatementsagreewiththeinformationgiveninReadingPassage1?WriteTRUEifthestatementagreeswiththei
A、Themanthinksthechildrenshouldhaveaplayroom.B、Thewomanhasn’tmadeuphermind.C、Themanobjectstotheexpense.D、
最新回复
(
0
)