首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图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-11-20
34
问题
设有向无环图G以邻接矩阵的方式存储,G
[j]中存放的是从结点i出发到结点j的边权,G
[j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。
根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
选项
答案
算法实现如下: int floyd(Graph G) { //构造一个新图 int dist[n][n]; //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][k]+dist[k][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://jikaoti.com/ti/TEfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
苏台德问题
战国初期,上党地区在下列哪一个国家的控制范围之内?()
文艺复兴运动兴起的时间是()。
1945年,联合国成立之时,创始会员国共有()个国家。
古希腊是西方文明的发源地,古希腊雅典的民主政治则开启了两方民主制度的先河。下列关于雅典民主政治的说法,符合史实的有()。①民主政治时期的雅典没有国王②公民大会是雅典国家的最高决策机构③伯里克利时期,雅典民主政治达到了顶峰④包括妇女在内的
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
1991年,南斯拉夫联邦解体,分裂为新国家的数目为()。
世界天文史上最早实地测量子午线的记录是由谁进行的?()
假定在~个8位字长的计算机中运行如下c程序段:unsignedintx=134;unsignedinty=246;intm=x;intn=y;unsignedintz1=x—y;
随机试题
在我国,确认土地承包经营权的主要依据是()。
Guthrie细菌生长抑制试验
Thebirdfluvirusismutatingandbecomingmoredangeroustomammals,accordingtoresearchers.Thediscoveryreinforcesfears
A.压缩骨折B.横行骨折C.斜行骨折D.粉碎骨折E.嵌插骨折骤然跪倒髌骨着地发生的髌骨骨折是
放射生物作用引起DNA和蛋白质构造变化的阶段是
孙某早年与妻子吕某离婚,儿子小强随吕某生活。小强15岁时,其祖父去世,孙某让小强参加葬礼。小强与祖父没有感情,加上吕某阻挡,未参加葬礼。从此,孙某就不再支付小强的抚养费用。吕某和小强向当地法院提起诉讼,请求责令孙某承担抚养费。在法庭上,孙某提出不承担抚养费
下列( )种组合能较全面而准确地表达投标报价的基本原则。Ⅰ、要保护投标方的经济利益Ⅱ、充分利用已有现场资料,优选经济合理的方案Ⅲ、详细研究分析招标文件中双方经济责任,根据承包方式,做到“内细算外粗报”,进行综合归纳Ⅳ、报价
随着人们生活水平的不断提高,越来越多的人开始外出旅游。如果在户外无定位的专门仪器,可借助地物来判定方向。下列是判断方位的方法,其中描述不正确的是()。
周某为了庆祝自己的18岁生日,与吴某达成了购买吴某饲养的波斯猫的合同,周某支付了价款,合同还约定,在周某生日的当天,吴某应亲自将波斯猫交付给周某。在周某生日那天,吴某带着波斯猫去周某家的路上不慎将波斯猫丢失。当日,陈某发现波斯猫后甚为喜欢,便带至家中细心喂
交换机命令可使用缩写形式,在Switch#模式下,键人con,则表示——。
最新回复
(
0
)