首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图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
112
问题
设有向无环图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://kaotiyun.com/show/2WRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述斯巴达克起义的原因、大体经过、意义和失败原因。
“灌木林原野事件”
1988年6月,苏联共产党第十九次代表会议的主题是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
第一个五年计划的具体时间段是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
下面哪部经典是我国最早的官方史书?()
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:若操作码0010B表示加法操作(助记符为ad
随机试题
债券基金的收益受市场利率的影响正确的是()。
()抽油机井热洗是为了防止蜡晶体在油管壁附着、聚集、长大而堵塞油管,影响油井正常生产的一种井筒加热措施。
姚纳的双重苦恼是什么?这段文字与前文构成何种关系?
朱砂安神丸治疗心悸最适用于
患者,女,26岁。孕2产1。现孕40周,来院途中分娩,总产程1小时,产后5天出现寒战、高热、下腹痛无乳胀及腹泻。妇科检查:阴道内有脓血,宫颈轻压裂伤,子宫大而软,压痛明显。首先考虑为
根据上述条件,估价人员适合选择的估价方法有()。根据上述条件,在开发完成后,该宗地土地无限年期最可能实现的价值是()。
论述孙中山南京临时政府在法制建设上的建树。
标识符在高级语言源程序中的作用不包括_____________。
若a是int型变量,则表达式(a=2*3,a*2),a+6的值为______。
Entertheinformationage.Informationistherawmaterialformanyofthebusinessactivities【C1】______thisnewera,justasir
最新回复
(
0
)