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

admin2017-11-20 67

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

1948年，南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法，其核心是()。

胡适与李大钊进行“问题与主义之争”的主战场是()。

为加强君权，皇太极时代开始直接控制的“上三旗”不包括()。

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

1628年出版了《心血运动论》一书，论证了血液在全身的循环运动，使生理学发展为科学的是()。

16世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

记载了用竿标日测影以求日高的方法，并认识了勾股定理的算书是()。

编写判定给定的二叉树是否是二叉排序树的函数。

为了保证行政组织的有序化，必须坚持行政发展的()

患者，男性，29岁，手部多发刀割伤后4小时，下列有关描述正确的是

咨询单位实现其发展战略的首要环节是()，承揽与本单位的业务范围和能力相适应的工程项目。

为KPI设定工作产出时，应当遵守()的原则。

下列是我国农村和城市每一名全国人大代表所代表的人口数比例变化表。这反映的实质问题是()

我国贯彻宗教信仰自由政策，依法加强对宗教事务的管理，主要目的是()。

在关系中凡能惟一标识元组的最小属性集称为该表的键或码。二维表中可能有若干个键，它们称为该表的()。

Accordingtothespeaker,whoisinneedoftheirhelp?

A、Theyhaveoverwhelmingadvantages.B、Theyaresoldinverylowprices.C、Theyarethesymbolofpeople’sstatus.D、Theymeetc

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

计算机408

学硕统考专业

1948年，南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法，其核心是()。

胡适与李大钊进行“问题与主义之争”的主战场是()。

为加强君权，皇太极时代开始直接控制的“上三旗”不包括()。

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

1628年出版了《心血运动论》一书，论证了血液在全身的循环运动，使生理学发展为科学的是()。

16世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

记载了用竿标日测影以求日高的方法，并认识了勾股定理的算书是()。

编写判定给定的二叉树是否是二叉排序树的函数。

为了保证行政组织的有序化，必须坚持行政发展的()

患者，男性，29岁，手部多发刀割伤后4小时，下列有关描述正确的是

咨询单位实现其发展战略的首要环节是()，承揽与本单位的业务范围和能力相适应的工程项目。

为KPI设定工作产出时，应当遵守()的原则。

下列是我国农村和城市每一名全国人大代表所代表的人口数比例变化表。这反映的实质问题是()

我国贯彻宗教信仰自由政策，依法加强对宗教事务的管理，主要目的是()。

在关系中凡能惟一标识元组的最小属性集称为该表的键或码。二维表中可能有若干个键，它们称为该表的()。

Accordingtothespeaker,whoisinneedoftheirhelp?

A、Theyhaveoverwhelmingadvantages.B、Theyaresoldinverylowprices.C、Theyarethesymbolofpeople’sstatus.D、Theymeetc

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