设有向无环图G以邻接矩阵的方式存储，G[i][j]中存放的是从结点i出发到结点j的边权，G[i][j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。给出算法的基本设计思想。

admin2017-04-28 73

问题设有向无环图G以邻接矩阵的方式存储，G[j]中存放的是从结点i出发到结点j的边权，G[j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。
给出算法的基本设计思想。

选项

答案基本设计思想：我们知道可以利用弗洛伊德算法(floyd)来求得图中任意两点间的最短路径长度，这里的边权是正数，如果图中所有的边权均为负数，那我们根据弗洛伊德算法求出的便是任意两点间最小的负权路径长度，此时若把所有的边权取相反数，则刚才求得的最短路径长度的相反数一定是现在的最长路径长度；根据此思想，将图G的边权改为它的相反数，得到图G’，然后用floyd算法对G’求出每对顶点间的最短路径，那么图G．中最短路径的相反数即为原图G的最长路径长度。

解析

转载请注明原文地址:https://kaotiyun.com/show/1WRi777K

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

设有向无环图G以邻接矩阵的方式存储，G[i][j]中存放的是从结点i出发到结点j的边权，G[i][j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。给出算法的基本设计思想。

计算机408

学硕统考专业

论述第二次鸦片战争的结局对中国社会有什么影响。

下列关于塞尔维乌斯改革的叙述错误的是()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

下列有关西欧封建社会的表述，错误的一项是()。

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

北约和华约两个组织对峙近半个世纪，这()。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2

巴比妥类药物可以在碱性条件下(硼砂溶液)用紫外分光光度法进行含量测定是因为：

酸枣仁除具有养心安神的功效外，还可以()。

企业的内部审计归结为监督、()和服务三个方面。

抵债资产应当是债务人所有或债务人依法享有处分权并且具有较强变现能力的财产，不包括()。

2007年前三季度，我国全社会固定资产投资91529亿元，同比增长25.7%。其中，城镇固定资产投资78247亿元，增长26.4%；农村投资13282亿元，增长21.2%。在城镇投资中，国有及国有控股完成投资33951亿元，增长16.2%；房地产开发完成投

下列叙述中正确的是()。

Childrenmodelthemselveslargelyontheirparents.Theydosomainlythroughidentification.Childrenidentify【C1】______parents

设有向无环图G以邻接矩阵的方式存储，G[i][j]中存放的是从结点i出发到结点j的边权，G[i][j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。 给出算法的基本设计思想。

计算机408

学硕统考专业

论述第二次鸦片战争的结局对中国社会有什么影响。

下列关于塞尔维乌斯改革的叙述错误的是()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

下列有关西欧封建社会的表述，错误的一项是()。

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

北约和华约两个组织对峙近半个世纪，这()。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2

巴比妥类药物可以在碱性条件下(硼砂溶液)用紫外分光光度法进行含量测定是因为：

酸枣仁除具有养心安神的功效外，还可以()。

企业的内部审计归结为监督、()和服务三个方面。

抵债资产应当是债务人所有或债务人依法享有处分权并且具有较强变现能力的财产，不包括()。

2007年前三季度，我国全社会固定资产投资91529亿元，同比增长25.7%。其中，城镇固定资产投资78247亿元，增长26.4%；农村投资13282亿元，增长21.2%。在城镇投资中，国有及国有控股完成投资33951亿元，增长16.2%；房地产开发完成投

下列叙述中正确的是()。

Childrenmodelthemselveslargelyontheirparents.Theydosomainlythroughidentification.Childrenidentify【C1】______parents

设有向无环图G以邻接矩阵的方式存储，G[i][j]中存放的是从结点i出发到结点j的边权，G[i][j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。给出算法的基本设计思想。