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

admin2017-04-28 41

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

学硕统考专业

在捍卫和传播生物进化论方面做出了贡献的是()。

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

以下关于国际联盟与联合国的表述，正确的是()。

典型的西欧封建庄园对农民采用的剥削方式是()。

第四点计划

北约和华约两个组织对峙近半个世纪，这()。

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

UNIX系统中，输入／输出设备看作是()。

简述群体规范形成的三个阶段。

诚信的道德要求人们诚善于心,言行一致。()

ALA合酶的辅酶是

个人不得购买的剧毒化学品是()。

Whileeveryoneisdifferent,therearcafewcommonthemesthatsurfaceforthosewithahistoryofabuse.Forinstance,it’sun

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

计算机408

学硕统考专业

在捍卫和传播生物进化论方面做出了贡献的是()。

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

以下关于国际联盟与联合国的表述，正确的是()。

典型的西欧封建庄园对农民采用的剥削方式是()。

第四点计划

北约和华约两个组织对峙近半个世纪，这()。

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

UNIX系统中，输入／输出设备看作是()。

简述群体规范形成的三个阶段。

诚信的道德要求人们诚善于心,言行一致。()

ALA合酶的辅酶是

个人不得购买的剧毒化学品是()。

Whileeveryoneisdifferent,therearcafewcommonthemesthatsurfaceforthosewithahistoryofabuse.Forinstance,it’sun

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