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

admin2017-11-20 40

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

学硕统考专业

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

我国发明生铁冶炼技术是在()。

汉章帝会群儒于白虎观，讨论经义，由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书，这部书系统地吸收了阴阳五行和谶纬之学，形成今文经学派的主要观点。

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

北约和华约两个组织对峙近半个世纪，其影响是()。

16世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

以孙中山为首的革命派和以康有为代表的维新派，是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()

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

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

下列关于侵权损害赔偿的说法，正确的是()。

女性，50岁，发现左乳肿块2个月，无自觉症状，体检左乳外上象限可触及3．5cm×3cm大小的质硬肿块，表面不光滑，边界不清晰，活动度小，表面局部皮肤凹陷，形似酒窝，肿块穿刺活检确诊为乳腺癌，出现皮肤凹陷提示()

孕妇妊娠9个月，时有腹中痛，痛定仍然如常。此为

根据《税收征管法》规定，以暴力、威胁方法拒不缴纳税款构成抗税罪的，处3年以下有期徒刑或者拘役。()

如果让你组织一次农民工职业技术培训，你会怎样组织?如何体现针对性和实效性?

改革、发展、稳定的关系是

Digitalphotographyisstillnewenoughthatmostofushaveyettoformanopinionaboutit,(1)_____developapointofview.

CPU主要技术性能指标有()。

Thiscountryisfullycommittedtotheintroductionofcomputersintoschools.Thisisdemonstratedbythefactthatvirtuallya

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

计算机408

学硕统考专业

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

我国发明生铁冶炼技术是在()。

汉章帝会群儒于白虎观，讨论经义，由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书，这部书系统地吸收了阴阳五行和谶纬之学，形成今文经学派的主要观点。

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

北约和华约两个组织对峙近半个世纪，其影响是()。

16世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

以孙中山为首的革命派和以康有为代表的维新派，是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()

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

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

下列关于侵权损害赔偿的说法，正确的是()。

女性，50岁，发现左乳肿块2个月，无自觉症状，体检左乳外上象限可触及3．5cm×3cm大小的质硬肿块，表面不光滑，边界不清晰，活动度小，表面局部皮肤凹陷，形似酒窝，肿块穿刺活检确诊为乳腺癌，出现皮肤凹陷提示()

孕妇妊娠9个月，时有腹中痛，痛定仍然如常。此为

根据《税收征管法》规定，以暴力、威胁方法拒不缴纳税款构成抗税罪的，处3年以下有期徒刑或者拘役。()

如果让你组织一次农民工职业技术培训，你会怎样组织?如何体现针对性和实效性?

改革、发展、稳定的关系是

Digitalphotographyisstillnewenoughthatmostofushaveyettoformanopinionaboutit,(1)_____developapointofview.

CPU主要技术性能指标有()。

Thiscountryisfullycommittedtotheintroductionofcomputersintoschools.Thisisdemonstratedbythefactthatvirtuallya

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