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

admin2017-04-28 78

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

概述太平天国运动失败的原因及历史意义。

《关于建国以来党的若干历史问题的决议》

文艺复兴运动兴起的时间是()。

下列关于俄国十月革命和德国十一月革命共同点的表述，不正确的是()。

明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。

火的使用，是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。

周王室的两大官僚系统是()。

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

某机采用计数器定时查询方式来进行总线判优控制，共有4个主设备竞争总线使用权，当汁数器初值恒为102时，4个主设备的优先级顺序为()。

泌尿系统感染的途径，可以是

从疾病的预防策略角度看，流行病学普查和筛检属于

以下说法不正确的是()。

“6C“标准原则的内容不包括()。

要坚持中国共产党的领导，必须加强和改进党的领导。加强和改进党的领导，一定要以科学理论作指导。“三个代表”重要思想之所以成为加强和改进党的建设的根本指导思想，是因为()。

当前我国具有综合性审批控制职能的行政组织系统是：

某人被判处死缓，在监狱里认真改造，有立功表现，后来给他减刑，他表现得越来越好。这个过程隐含的行为塑造原理有()

It’snotdifficulttosettargetsforstaff.Itismuchharder,【B1】________,tounderstandtheirnegativeconsequences.Mostwor

MargheritaisaLondongirlandarrivingatCapitalwaslikecominghome."IgrewuplisteningtoCapitalRadio,"shesays."Peo

Ihavetakenmanyphotos.I’mgoingtogetthefilm______.

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

计算机408

学硕统考专业

概述太平天国运动失败的原因及历史意义。

《关于建国以来党的若干历史问题的决议》

文艺复兴运动兴起的时间是()。

下列关于俄国十月革命和德国十一月革命共同点的表述，不正确的是()。

明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。

火的使用，是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。

周王室的两大官僚系统是()。

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

某机采用计数器定时查询方式来进行总线判优控制，共有4个主设备竞争总线使用权，当汁数器初值恒为102时，4个主设备的优先级顺序为()。

泌尿系统感染的途径，可以是

从疾病的预防策略角度看，流行病学普查和筛检属于

以下说法不正确的是()。

“6C“标准原则的内容不包括()。

要坚持中国共产党的领导，必须加强和改进党的领导。加强和改进党的领导，一定要以科学理论作指导。“三个代表”重要思想之所以成为加强和改进党的建设的根本指导思想，是因为()。

当前我国具有综合性审批控制职能的行政组织系统是：

某人被判处死缓，在监狱里认真改造，有立功表现，后来给他减刑，他表现得越来越好。这个过程隐含的行为塑造原理有()

It’snotdifficulttosettargetsforstaff.Itismuchharder,【B1】________,tounderstandtheirnegativeconsequences.Mostwor

MargheritaisaLondongirlandarrivingatCapitalwaslikecominghome."IgrewuplisteningtoCapitalRadio,"shesays."Peo

Ihavetakenmanyphotos.I’mgoingtogetthefilm______.

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