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

admin2017-04-28 34

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

学硕统考专业

简述斯巴达克起义的原因、大体经过、意义和失败原因。

在欧盟发展历史上，促使欧盟正式成立的文件是()。

下列哪个文件标志着“文化大革命”的发起?()

隋朝建立了三省六部制，其中负责审议的部门是()。

主张对义和团实行安抚策略的是()。

在周初分封中，分封同姓诸侯国、异姓诸侯国，也分封圣王之后，下面属于圣王之后的封国为()。

[*]对应的微指令如下：ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001

汉语方言可以分为七大方言区，即北方或官话方言、吴方言、湘方言、赣方言、客家方言、闽方言和粤方言。()

论述持有至到期投资的实质性程序。

心包腔积液的穿刺抽液可在何处进针?并试述其解剖学依据。

A、腹部叩诊移动性浊音B、呕吐咖啡色液C、脑膜刺激征D、不能唤醒有浅反射E、昏迷病人呼吸有烂苹果味浅昏迷时

建设项目中间评价通常也称为()。

某分部工程双代号时标网络计划如下图所示．该计划所提供的正确信息有()。

Doyouenjoylisteningtorecords?Ifindrecordsareoften______orbetterthananactualperformance.

A、Theyarenotasdangerousaspeoplethink.B、Theycanbeasfriendlytohumansasdogs.C、Theyattackhumanbeingsbynature.

Isitcheapertobeawoman—oraman?A)Tocelebratethelaunchofgenderequalityinfinancialservices,Moneyexploredothera

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

计算机408

学硕统考专业

简述斯巴达克起义的原因、大体经过、意义和失败原因。

在欧盟发展历史上，促使欧盟正式成立的文件是()。

下列哪个文件标志着“文化大革命”的发起?()

隋朝建立了三省六部制，其中负责审议的部门是()。

主张对义和团实行安抚策略的是()。

在周初分封中，分封同姓诸侯国、异姓诸侯国，也分封圣王之后，下面属于圣王之后的封国为()。

[*]对应的微指令如下：ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001

汉语方言可以分为七大方言区，即北方或官话方言、吴方言、湘方言、赣方言、客家方言、闽方言和粤方言。()

论述持有至到期投资的实质性程序。

心包腔积液的穿刺抽液可在何处进针?并试述其解剖学依据。

A、腹部叩诊移动性浊音B、呕吐咖啡色液C、脑膜刺激征D、不能唤醒有浅反射E、昏迷病人呼吸有烂苹果味浅昏迷时

建设项目中间评价通常也称为()。

某分部工程双代号时标网络计划如下图所示．该计划所提供的正确信息有()。

Doyouenjoylisteningtorecords?Ifindrecordsareoften______orbetterthananactualperformance.

A、Theyarenotasdangerousaspeoplethink.B、Theycanbeasfriendlytohumansasdogs.C、Theyattackhumanbeingsbynature.

Isitcheapertobeawoman—oraman?A)Tocelebratethelaunchofgenderequalityinfinancialservices,Moneyexploredothera

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