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

admin2017-11-20 61

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

巴黎和会上，英国既与法国联合抵制美国称霸世界，又与美国联合反对法国过分削弱德国的要求，英国这样做的目的是()。

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

中华人民共和国恢复了在联合国合法席位的时间是()。

在巴黎和会上获利最大的两个国家是()。

解放军渡江战役中横渡长江的东西两个攻击点是()。

下列关于第二三次科技革命的说法，不正确的是()。

我国生铁冶炼技术最早出现于()。

以孙中山为首的革命派和以康有为代表的维新派，是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()

假定在～个8位字长的计算机中运行如下c程序段：unsignedintx=134;unsignedinty=246；intm=x；intn=y；unsignedintz1=x—y；

急性肾衰竭血液透析指征为

中年男性患者，发现视力下降2天，右眼视力降至0．5，左眼0．6，眼底检查发现双眼视盘边界稍模糊，视盘充血。黄斑部可疑水肿。证实这一诊断的重要检查应当包括

下列不属于药物衣的是

在进行桥梁承载能力检算时，承载能力检算系数Z1作为结构抗力效应的修正系数，其值不大于1。()

下列关于商用房贷款的签约流程表述错误的是()。

下列事项中，应确认预计负债的有()。

下列权力不属于公安机关的侦查权的是()

A、76B、123C、171D、514B前两个圆圈中数字的规律：11×2＋25＋7＝54,36×2＋29＋5＝106,则问号处数字应为7×9＋13＋47＝123,故选B。

AnOhioStateUniversitystudyhaslinkedbehaviorinyoungchildren【1】thetypeofjobtheirmotherhas.Motherswithcomplexoc

A、Shepainteditbyherself.B、Shehiredherbrothertopaintit.C、Itneedstobepainted.D、Itisn’tbeautifullypainted.B语义理

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

计算机408

学硕统考专业

巴黎和会上，英国既与法国联合抵制美国称霸世界，又与美国联合反对法国过分削弱德国的要求，英国这样做的目的是()。

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

中华人民共和国恢复了在联合国合法席位的时间是()。

在巴黎和会上获利最大的两个国家是()。

解放军渡江战役中横渡长江的东西两个攻击点是()。

下列关于第二三次科技革命的说法，不正确的是()。

我国生铁冶炼技术最早出现于()。

以孙中山为首的革命派和以康有为代表的维新派，是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()

假定在～个8位字长的计算机中运行如下c程序段：unsignedintx=134;unsignedinty=246；intm=x；intn=y；unsignedintz1=x—y；

急性肾衰竭血液透析指征为

中年男性患者，发现视力下降2天，右眼视力降至0．5，左眼0．6，眼底检查发现双眼视盘边界稍模糊，视盘充血。黄斑部可疑水肿。证实这一诊断的重要检查应当包括

下列不属于药物衣的是

在进行桥梁承载能力检算时，承载能力检算系数Z1作为结构抗力效应的修正系数，其值不大于1。()

下列关于商用房贷款的签约流程表述错误的是()。

下列事项中，应确认预计负债的有()。

下列权力不属于公安机关的侦查权的是()

A、76B、123C、171D、514B前两个圆圈中数字的规律：11×2＋25＋7＝54,36×2＋29＋5＝106,则问号处数字应为7×9＋13＋47＝123,故选B。

AnOhioStateUniversitystudyhaslinkedbehaviorinyoungchildren【1】thetypeofjobtheirmotherhas.Motherswithcomplexoc

A、Shepainteditbyherself.B、Shehiredherbrothertopaintit.C、Itneedstobepainted.D、Itisn’tbeautifullypainted.B语义理

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