首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图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
28
问题
设有向无环图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
学硕统考专业
相关试题推荐
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
下列关于古日耳曼人的社会状况的叙述中,不正确的是()。
下列事件:①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订,按照时间顺序排列正确的是()。
论述古王国君主专制的表现。
第一个五年计划的具体时间段是()。
在巴黎和会上,法国要求严厉制裁德国的目的是()。
论述新石器时代及其文化类型。
把变量引进数学。使解析几何成为数学发展史上转折点的科学家是()。
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
某虚拟存储系统中有一个进程共有6页(0~5),其中代码占3页(0~2),数据占1页(3),数据堆占1页(4),用户栈占1页(5)。它们依次存放在外存的22,23,25,26存储块。当前,代码页已经分配在物理内存的66,67,87页,数据页为31,并已经进行
随机试题
焊接结构易产生脆断的原因是什么?
根据《担保法》的规定,下列选项中,可用于抵押的是()
割裂感性认识和理性认识的辩证统一,会导致两种错误理论,一种是经验论,另一种是【】
【案例】患者男,58岁。吸烟史30年,咳嗽咳痰20余年,活动后气短4年,偶有下肢水肿。近5天咳嗽、气短症状加重。查体:神志清,桶状胸,双肺呼吸音低,少量湿啰音,P2>A2,剑突下搏动增强,双下肢水肿。关于肺动脉高压下列描述正确的是
治疗肋骨骨折后疼痛,最有效的方法
某市政桥梁工程,总包方A市政公司将钢梁安装工程分包给B安装公司。总包方A公司制定了钢梁吊装方案并得到监理工程师的批准。由于工期紧,人员紧缺,B公司将刚从市场招聘的李某与高某经简单内部培训组成吊装组。某日清晨,雾气很浓,能见度较低,吊装组就位,准备对刚组装
人体运动是在神经系统支配下,以肌肉收缩为动力,关节为轴,骨骼为杠杆完成的。()
教师职业的最大特点在于职业角色的()。
教师在教育工作中要做到循序渐进,这是因为()。
AgingposesaseriouschallengetoOECD(OrganizationofEconomicCo-operationandDevelopment)countries,inparticular,howto
最新回复
(
0
)