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

admin2017-11-20 83

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

学硕统考专业

在巴黎和会上获利最大的两个国家是()。

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

詹天佑自主设计修建了中国第一条铁路是在()。

在巴黎和会上，法国要求严厉制裁德国的目的是()。

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

在罗斯福新政期间，美国政府在森林中修筑铁路，力图为美国青年人提供更多的工作机会。这种举措有利于()。①缓和阶级矛盾和安定社会秩序②扩大消费，刺激经济复苏③根除资本主义经济危机④消除资本主义社会的基本矛盾

中国革命必须走农村包围城市的道路，其主要依据是()

A．Osier结B．Ewart征C．肝脏扩张性搏动D．Duroziez氏血管杂音E．Beck三联征

患者，女，32岁，不慎外阴受伤，20分钟后出现外阴肿物，疼痛难忍，最可能的诊断是

下列哪项不是甘草的粉末特征（　　）。

在国际债券市场上，不需要官方主管机构批准，也不受货币发行国有关法令管制和约束的债券是()。

一般认为，金融工具具有流动性、风险性和收益性的特征。()

禁止与取缔，是指公安机关依法对某些犯罪行为和违反治安管理、扰乱社会秩序、妨害公共安全的行为宣布禁止，予以取缔，并对违禁者予以法律制裁。(　　)

自顶向下规划的重要目标是达到信息的一致性，即保证下列()的一致。Ⅰ．数字字段定义Ⅱ．数据结构Ⅲ．更新时间Ⅳ．更新规划Ⅴ．数据记录

将内部专用IP地址转换为外部公用IP地址的技术是（）。

若有以下程序段intr=8;printf("%d\n",r＞＞1);输出结果是

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

计算机408

学硕统考专业

在巴黎和会上获利最大的两个国家是()。

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

詹天佑自主设计修建了中国第一条铁路是在()。

在巴黎和会上，法国要求严厉制裁德国的目的是()。

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

在罗斯福新政期间，美国政府在森林中修筑铁路，力图为美国青年人提供更多的工作机会。这种举措有利于()。①缓和阶级矛盾和安定社会秩序②扩大消费，刺激经济复苏③根除资本主义经济危机④消除资本主义社会的基本矛盾

中国革命必须走农村包围城市的道路，其主要依据是()

A．Osier结B．Ewart征C．肝脏扩张性搏动D．Duroziez氏血管杂音E．Beck三联征

患者，女，32岁，不慎外阴受伤，20分钟后出现外阴肿物，疼痛难忍，最可能的诊断是

下列哪项不是甘草的粉末特征（ ）。

在国际债券市场上，不需要官方主管机构批准，也不受货币发行国有关法令管制和约束的债券是()。

一般认为，金融工具具有流动性、风险性和收益性的特征。()

禁止与取缔，是指公安机关依法对某些犯罪行为和违反治安管理、扰乱社会秩序、妨害公共安全的行为宣布禁止，予以取缔，并对违禁者予以法律制裁。( )

自顶向下规划的重要目标是达到信息的一致性，即保证下列()的一致。Ⅰ．数字字段定义Ⅱ．数据结构Ⅲ．更新时间Ⅳ．更新规划Ⅴ．数据记录

将内部专用IP地址转换为外部公用IP地址的技术是（）。

若有以下程序段intr=8;printf("%d\n",r＞＞1);输出结果是

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

下列哪项不是甘草的粉末特征（　　）。

禁止与取缔，是指公安机关依法对某些犯罪行为和违反治安管理、扰乱社会秩序、妨害公共安全的行为宣布禁止，予以取缔，并对违禁者予以法律制裁。(　　)