设有向无环图G以邻接矩阵的方式存储，G[i][j]中存放的是从结点i出发到结点j的边权，G[i][j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

admin2017-11-20 88

问题设有向无环图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://www.kaotiyun.com/show/oNRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

设有向无环图G以邻接矩阵的方式存储，G[i][j]中存放的是从结点i出发到结点j的边权，G[i][j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

计算机408

学硕统考专业

夏王朝建立后，将其领土划分为九州，派九牧进行治理，在九州范围内根据土地的肥沃程度缴纳贡赋，称为()。

晚清时期清帝年号的正确排序是()

1905年至1907年间，围绕中国究竟是采用革命手段还是改良方式这个问题，革命派与改良派进行论战的舆论阵地是()。

洋务派创办军事工业的方式是()。

克里特文明的文字类型是()。

明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。

玛雅人的金字塔主要功能是()。

在西欧列强海外殖民扩张进程中，各国之间相互争夺海上霸权。18世纪末，英国在争霸中取得胜利的根本原因在于()

某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int和shorI型长度分别为32位和16位，并且数据按边界对齐存储。某C语言程序段如下：struct{inta：charb：shOrtc：}record：record.a=273：

师生关系在_______上是相互促进的关系。

建筑工程施工现场环境保护要求中，施工现场产生的固体废弃物应在所在地县级以上地方人民政府()部门申报登记，分类存放。

关于施工成本计划的说法中，错误的是()。

甲、乙、丙三个国有企业共同投资设立某有限责任公司，设立了董事会和监事会。股东会通过的下列决议中，不符合公司法律制度规定的有()。

甲企业拥有一处原值560000元的房产。已知房产税税率为1．2％，当地规定的房产税减除比例为30％。甲企业年应缴纳房产税税额的下列计算中，正确的是()。

某企业实施质量改进项目，采用网络图法。根据所搜集的资料绘制的网络图如图6.4—6所示。根据图形可分析出：确定关键线路，便于()。

以下各项中，哪个选项2006年的产业值最大(　)。根据材料，2005年浙江省的工业总产值约为(　)。

对调用数据库数据的命令进行语法、语义和权限检查的信息，存储于下列哪一个(些)结构中?

设有向无环图G以邻接矩阵的方式存储，G[i][j]中存放的是从结点i出发到结点j的边权，G[i][j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

计算机408

学硕统考专业

夏王朝建立后，将其领土划分为九州，派九牧进行治理，在九州范围内根据土地的肥沃程度缴纳贡赋，称为()。

晚清时期清帝年号的正确排序是()

1905年至1907年间，围绕中国究竟是采用革命手段还是改良方式这个问题，革命派与改良派进行论战的舆论阵地是()。

洋务派创办军事工业的方式是()。

克里特文明的文字类型是()。

明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。

玛雅人的金字塔主要功能是()。

在西欧列强海外殖民扩张进程中，各国之间相互争夺海上霸权。18世纪末，英国在争霸中取得胜利的根本原因在于()

某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int和shorI型长度分别为32位和16位，并且数据按边界对齐存储。某C语言程序段如下：struct{inta：charb：shOrtc：}record：record.a=273：

师生关系在_______上是相互促进的关系。

建筑工程施工现场环境保护要求中，施工现场产生的固体废弃物应在所在地县级以上地方人民政府()部门申报登记，分类存放。

关于施工成本计划的说法中，错误的是()。

甲、乙、丙三个国有企业共同投资设立某有限责任公司，设立了董事会和监事会。股东会通过的下列决议中，不符合公司法律制度规定的有()。

甲企业拥有一处原值560000元的房产。已知房产税税率为1．2％，当地规定的房产税减除比例为30％。甲企业年应缴纳房产税税额的下列计算中，正确的是()。

某企业实施质量改进项目，采用网络图法。根据所搜集的资料绘制的网络图如图6.4—6所示。根据图形可分析出： 确定关键线路，便于()。

以下各项中，哪个选项2006年的产业值最大( )。根据材料，2005年浙江省的工业总产值约为( )。

对调用数据库数据的命令进行语法、语义和权限检查的信息，存储于下列哪一个(些)结构中?

设有向无环图G以邻接矩阵的方式存储，G[i][j]中存放的是从结点i出发到结点j的边权，G[i][j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

某企业实施质量改进项目，采用网络图法。根据所搜集的资料绘制的网络图如图6.4—6所示。根据图形可分析出：确定关键线路，便于()。

以下各项中，哪个选项2006年的产业值最大(　)。根据材料，2005年浙江省的工业总产值约为(　)。