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

admin2017-11-20 85

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

魏晋南北朝的手工业技术有所进步，下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料

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

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。

下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削，工匠的人身依附关系加强

宁夏回族自治区的设立时间是()。

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

下列关于二尖瓣关闭不全听诊特点的叙述，正确的是

下列有脾破裂的分型及描述，错误的是

患者不明原因近年来进行性肥胖，因半年来闭经就诊。查体：发现其向心性肥胖，面部、胸部都有痤疮，下腹部皮肤有紫纹，BP22．00／13．33kPa(1mmHg=0．133kPa)，血糖8．5mmol／d1，血皮质醇46mg／dl。提问1：最可能的诊断为

女性，32岁，诊断为淋病，治疗应首选

甲、乙二人各出资5万元购买了一套商品房，轮流居住，在甲居住期间因连降大雨，房屋倒塌，砸伤行人丙。丙应当向谁主张权利?

在中共八大上，陈云提出了关于我国社会主义经济体制的设想，其主要点包括()

MediaandCurrentEventsThemediacanimpactcurrentevents.AsagraduatestudentatBerkeleyinthe1960s,Irememberexp

Howmanylevelsarereservedforemployeeparking?

毫无疑问，有些妇女坚持要有离婚的权利，如果她们的丈夫干的工作和积攒的钱不如她们多的话。

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

计算机408

学硕统考专业

魏晋南北朝的手工业技术有所进步，下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料

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

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。

下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削，工匠的人身依附关系加强

宁夏回族自治区的设立时间是()。

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

下列关于二尖瓣关闭不全听诊特点的叙述，正确的是

下列有脾破裂的分型及描述，错误的是

患者不明原因近年来进行性肥胖，因半年来闭经就诊。查体：发现其向心性肥胖，面部、胸部都有痤疮，下腹部皮肤有紫纹，BP22．00／13．33kPa(1mmHg=0．133kPa)，血糖8．5mmol／d1，血皮质醇46mg／dl。提问1：最可能的诊断为

女性，32岁，诊断为淋病，治疗应首选

甲、乙二人各出资5万元购买了一套商品房，轮流居住，在甲居住期间因连降大雨，房屋倒塌，砸伤行人丙。丙应当向谁主张权利?

在中共八大上，陈云提出了关于我国社会主义经济体制的设想，其主要点包括()

MediaandCurrentEventsThemediacanimpactcurrentevents.AsagraduatestudentatBerkeleyinthe1960s,Irememberexp

Howmanylevelsarereservedforemployeeparking?

毫无疑问，有些妇女坚持要有离婚的权利，如果她们的丈夫干的工作和积攒的钱不如她们多的话。

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