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

admin2017-11-20 44

问题设有向无环图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

学硕统考专业

西欧早期资产阶级反封建斗争以反天主教会的方式进行，主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起

提出电磁感应定律的是物理学家()。

第一国际成立前，各国无产阶级强烈要求加强国际团结的直接原因是()。

巴黎和会上，英美主张把原德国在山东的权利转让给日本，华盛顿会议又表示支持中国让日本归还山东的要求，英美态度发生变化的根本原因是()。

宋代由于旧坊制被打破，城市中行业分区性逐渐消失，北宋政府通过()来控制商人和商业。

论述新石器时代及其文化类型。

试析第三次科学技术革命对人类社会和历史进程的影响。

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化在类型上可以分为()

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

古立克指出，________作出的任意裁决最多。

患者将墙上的灯的影子看成是一个怪兽，此症状是

以下选项叙述正确的是()。

(2013年)我国反垄断法律制度禁止具有市场支配地位的经营者，无正当理由以低于成本的价格销售商品。下列各项中，属于法定正当理由的有()。

业主可以根据不同情况采用不同形式对物业进行管理，下列说法错误的是()。

在我国古代诗词中，杨柳是较为常见的意象，往往蕴涵离别之情，下列名句中不是表达送别意象的是()。

2

构成网络协议的三要素是()。

Moreoftheworld’shotchiles______fromCentralMexicothanfromanyotherpartoftheworld.

Keepingafullsocialcalendarmayhelpprotectyoufromdementia(痴呆症),researcherssaidonMonday.【C1】______activepeople

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

计算机408

学硕统考专业

西欧早期资产阶级反封建斗争以反天主教会的方式进行，主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起

提出电磁感应定律的是物理学家()。

第一国际成立前，各国无产阶级强烈要求加强国际团结的直接原因是()。

巴黎和会上，英美主张把原德国在山东的权利转让给日本，华盛顿会议又表示支持中国让日本归还山东的要求，英美态度发生变化的根本原因是()。

宋代由于旧坊制被打破，城市中行业分区性逐渐消失，北宋政府通过()来控制商人和商业。

论述新石器时代及其文化类型。

试析第三次科学技术革命对人类社会和历史进程的影响。

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化在类型上可以分为()

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

古立克指出，________作出的任意裁决最多。

患者将墙上的灯的影子看成是一个怪兽，此症状是

以下选项叙述正确的是()。

(2013年)我国反垄断法律制度禁止具有市场支配地位的经营者，无正当理由以低于成本的价格销售商品。下列各项中，属于法定正当理由的有()。

业主可以根据不同情况采用不同形式对物业进行管理，下列说法错误的是()。

在我国古代诗词中，杨柳是较为常见的意象，往往蕴涵离别之情，下列名句中不是表达送别意象的是()。

2

构成网络协议的三要素是()。

Moreoftheworld’shotchiles______fromCentralMexicothanfromanyotherpartoftheworld.

Keepingafullsocialcalendarmayhelpprotectyoufromdementia(痴呆症),researcherssaidonMonday.【C1】______activepeople

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