首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图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
89
问题
设有向无环图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
学硕统考专业
相关试题推荐
古代两河流域最具代表性的文学作品是()。
关于德国工业革命,说法不正确的是()。
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
下列关于清朝军机处的叙述,不正确的是()。
胡适与李大钊进行“问题与主义之争”的主战场是()。
1947年,苏联一些农村的干部和群众,为了调动广大群众生产积极性,在管理制度方面进行改革,其主要措施是()。
中古时代实行索贡巡行赋税征收方式的国家是()。
林则徐主持编译的《四洲志》,介绍了世界各国的史地。鸦片战争后,主要以《四洲志》为基础成书的重要著作是()
编写判定给定的二叉树是否是二叉排序树的函数。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
随机试题
以下属于茶艺人员佩戴发饰、头饰注意事项的有
送上级机关仲裁用的样品在运送前应对样品进行
女,28岁。连续发热1月,关节痛,G1P1,白细胞为3.4×109/L,血红蛋白98g/L,血小板200×109/L,血沉76mm/h,尿红细胞(+),尿蛋白(++),抗核抗体1:3.2。哪项表明肾损害
通过刷牙不能有效地达到()。
材料采购合同签定后,对于实行供货方送货的物资,采购方违反合同规定拒绝接货,要承担( )。
设备寿命分为()。
“破窗理论”是一经济学名词。原意是玻璃门窗被砸破,虽然造成一定的损失,但由此带来玻璃制造商、建筑商受益,引发新的建设链条发展,从而拉动经济增长。“破窗理论”主要体现了______。
在某次学术会议上,有人发现:凡是认识李博士的人,张教授都认识;只要是有些人不认识的人,赵研究员全都认识;新参加会议的研究生小王不认识与会的任何人。根据以上陈述,可以得出
我【151】地记得,第一次见到他是在北京的一个舞厅里。他穿的很特别,跳舞的【152】酷酷的,非常迷人。周围的观众都被他吸引住了,都在目不转睛地欣赏着。当音乐结束的时候,全场【153】出热烈的掌声,我更是使劲地鼓掌,真想跑上去跟他拥抱一下儿。但【154】我很
Anordinarysubwaytrain,approachingthestation,canbe________theloudestjet.
最新回复
(
0
)