首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图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
26
问题
设有向无环图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://kaotiyun.com/show/oNRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
下列对春秋时期各国称霸的顺序描述错误的选项是()
1946年5月,中共中央发布的实现“耕者有其田”政策的重要文件是()。
1951年参加西藏和平谈判的双方代表团首席代表是()。
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
关于东晋末年农民起义的表述中,不正确的是()
“两个凡是”
詹天佑自主设计修建了中国第一条铁路是在()。
火的使用,是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
随机试题
我国国家赔偿法的归责原则是违法原则,下列对违法的含义正确的理解是()。
Ipassedmyexamsbutitwasalongtime______myfriendsaboutit.
男性,65岁,反复咳嗽、咳痰30余年,心悸、气促、下肢间歇性水肿3年,病情加重伴畏寒发热1周入院。体检:T:38℃,呼吸急促,口唇发绀,双肺叩诊过清音,中下肺有湿哕音,心率110次/分,心律齐,无杂音,双下肢重度水肿。假设该病例呼吸困难,突然进一步加
人参、鹿茸、冬虫夏草等中药都是人们非常喜爱的中药材,能够滋补身体,增强人体免疫力。丹参也是人们非常广泛使用的中药,它的功效有
根据合同法律制度的规定,下列各项中,( )属于可撤销要约的情形。
某企业为增值税一般纳税人,兼营增值税应税项目和免税项目。2010年5月应税项目取得不含税销售额1200万元,适用税率17%,免税项目取得销售额1000万元;当月购进用于应税项目的材料支付价款。700万元,适用税率17%,购进用于免税项目的材料支付价款400
《桃花源记》中描述:“缘溪行,忘路之远近。忽逢桃花林,……林尽水源,便得一山,山有小口,仿佛若有光。便舍船,从口入。初极狭,才通人。复行数十步,豁然开朗。土地平旷,屋舍俨然,有良田美池桑竹之属。”“桃花源”的地形最可能是()。
教育形成自己相对独立形态的标志是()。
他胜任这项工作,这是毫无疑问的。
EveryonereadssomethingaboutSherlockHolmes,whoisoneoftheworld’sgreatestdetectives.Theinventor,SirArthurIgnatius
最新回复
(
0
)