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

admin2017-04-28 83

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

学硕统考专业

【奥地利王位继承战争】南京大学2013年国际关系史真题

1895年发现X射线，拉开物理学革命序幕的科学家是()。

拜占庭建筑风格的典型代表圣索菲亚大教堂建于()。

洋务派创办军事工业的方式是()。

在1875年宪法中关于法国立法权的叙述，不正确的是()。

“钟鸣鼎食”往往用来形容贵族生活。考古发现的青铜乐器“钟”始见于周代遗址，可能存在于()

二战后世界经济走向统一的过程中，仍然存在着多样性，出现了“两种体系、三种国家”，下列不属于社会主义国家经济类型的是()。

某定点机字长8位(含1位符号位)，现该机中一个寄存器的内容为43H，则将其算术左移一位、算术右移一位的结果分别为()。

风湿热的发病机制中下列哪项是不恰当的

28岁，初孕妇，妊娠39周，肋下有块状物，子宫呈纵椭圆形，胎先露部较软且不规则，胎心在脐上偏左

根据我国增值税法的规定，增值税的征税范围包括：()。

统一拆迁是由掌握拆迁政策、法规及具备拆迁技术的拆迁人,实施本单位建设项目的房屋拆迁工作。()

事业单位购入的固定资产，其成本包括购买价款、相关税费以及固定资产交付使用前所发生的可归属于该项资产的运输费、装卸费、安装调试费和专业人员服务费。()

期望效应说明()

哲学基本问题的第一方面即物质和精神何者为第一性问题是()。

OffersWe’llrefund3XthedifferenceWithournewPRICEWATCHpromiseonselecteditemsweaimtoofferthe

A、Itwillbringherpotentialintofullplay.B、Itwillinvolvelotsoftraintravel.C、ItwillenablehertoimproveherChines

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

计算机408

学硕统考专业

【奥地利王位继承战争】南京大学2013年国际关系史真题

1895年发现X射线，拉开物理学革命序幕的科学家是()。

拜占庭建筑风格的典型代表圣索菲亚大教堂建于()。

洋务派创办军事工业的方式是()。

在1875年宪法中关于法国立法权的叙述，不正确的是()。

“钟鸣鼎食”往往用来形容贵族生活。考古发现的青铜乐器“钟”始见于周代遗址，可能存在于()

二战后世界经济走向统一的过程中，仍然存在着多样性，出现了“两种体系、三种国家”，下列不属于社会主义国家经济类型的是()。

某定点机字长8位(含1位符号位)，现该机中一个寄存器的内容为43H，则将其算术左移一位、算术右移一位的结果分别为()。

风湿热的发病机制中下列哪项是不恰当的

28岁，初孕妇，妊娠39周，肋下有块状物，子宫呈纵椭圆形，胎先露部较软且不规则，胎心在脐上偏左

根据我国增值税法的规定，增值税的征税范围包括：()。

统一拆迁是由掌握拆迁政策、法规及具备拆迁技术的拆迁人,实施本单位建设项目的房屋拆迁工作。()

事业单位购入的固定资产，其成本包括购买价款、相关税费以及固定资产交付使用前所发生的可归属于该项资产的运输费、装卸费、安装调试费和专业人员服务费。()

期望效应说明()

哲学基本问题的第一方面即物质和精神何者为第一性问题是()。

OffersWe’llrefund3XthedifferenceWithournewPRICEWATCHpromiseonselecteditemsweaimtoofferthe

A、Itwillbringherpotentialintofullplay.B、Itwillinvolvelotsoftraintravel.C、ItwillenablehertoimproveherChines

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