首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图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
88
问题
设有向无环图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://www.kaotiyun.com/show/2WRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1876年7月第一国际举行最后一次代表大会宣告解散,这次代表大会的地点是()。
下列哪一项不是凯末尔世俗化改革的内容?()。
下列关于清朝军机处的叙述,不正确的是()。
下面哪项条约没有涉及德国的赔款问题?()
元朝在中央设置中书省、地方则设置行中书省,其目的是()。
克里特文明的文字类型是()。
周人重视婚姻,对婚礼尤为讲究。周代的婚礼有六项程序,即:①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()
在周初分封中,分封同姓诸侯国、异姓诸侯国,也分封圣王之后,下面属于圣王之后的封国为()。
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
在操作系统中,P,V操作是一种()。
随机试题
关于“与下级往来”账户的说明,正确的是()
(2003)Thechildreninourfamilyarealways______totheirelders.
男,5岁,肘部外伤,用哪种体征来鉴别肱骨髁上骨折和肘关节脱位最可靠
根据《宪法》的规定,关于宪法文本的内容,下列哪一选项是正确的?(2013年卷一第21题)
市场中最基本的市场关系有()。
根据下列资料,回答下列问题。2013年1~7月份,某市规模以上工业增加值同比增长12.0%,增速比去年同期提高1.4个百分点。1~7月份,全市国有及国有控股企业完成增加值同比下降3.5%;民营企业完成增加值同比增长24.8%:外商控股企业完成增加值同比
从所给的四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性:
下列关于WindowsServer2003系统下DHCP服务器“排除”和“保留”的描述中,错误的是()。
下列内容不属于VBA提供的数据验证的函数是()。
SpeakerA:Fredisfrequentlylate,butthisisridiculous.Whydon’twegoinside?SpeakerB:______
最新回复
(
0
)