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

admin2017-04-28 62

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

选项

答案时间复杂度分析：因为用到了floyd算法，而遍历新图用到的是两层循环(小于O(n³))，故时间复杂度为O(n³)（n代表节点的个数）。

解析

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

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

计算机408
学硕统考专业

相关试题推荐

如何全面分析十月革命的历史条件及特点?
《关于建国以来党的若干历史问题的决议》
关于斯巴达的论述错误的是()。
诸侯国的国君如何用人呢?有人主张：“左右皆曰不可，勿听；诸大夫皆曰不可，勿听；国人皆曰不可，然后察之，见不可焉，然后去之。”这种主张最终可能出自下列哪位思想家之口()。
“瓜步之战”发生在下列哪两个政权之间?()
巴黎和会召开的时间是()。
明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。
世界近代史上，世界经济发展经历了两次大的飞跃，即第一次工业革命和第二次工业革命。阅读下面两段材料，回答问题：材料一工业革命的主角——蒸汽机，是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产，主要依靠以人力和经
一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2
某系统有R1、R2和R3共3种资源，在TO时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况如表4-4所示，此时系统的可用资源向量为(2，1，2)。试问：将系统中各种资源总数和此刻各进程对各资源的需求个数用向量或矩阵表示出来。

随机试题

为什么要实施融合战略?其实施的因素与条件是什么?
《千金方》中主治蓄血证的方剂是《内外伤辨惑论》中的半夏白术天麻汤源于
医学伦理学的指导原则有
关于混合式招标，下列说法错误的是()。
在前期物业管理期间，物业管理公司提供的服务，既包含物业正常使用期间的常规性服务，也包括()等前期物业管理的特殊内容。
产生遗嘱继承法律关系的法律事实是()
某公司行政部人员手机使用情况如下：(1)小王拨打过行政部所有人的电话；(2)小李曾经拨打过小赵的电话，但是小赵不曾拨打过其他人的电话；(3)不曾接听来自行政部人员电话的人也就不曾拨打过其他人的电话。由此可以推出：
有关系R(A，B，C）和关系S(A，D，E，F)。如果将关系代数表达式πR.A.R.B.S.D.S.F(RS)用SQL的查询语句来表示，则有：SELECTR.A，R.B，S.D，S.FFROMR，SWHERE【】。
【B1】【B15】
Themanageratoncelosthis______whenhelearntthathissecretarywaslateagainforthemeeting.

最新回复(0)

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

计算机408

学硕统考专业

如何全面分析十月革命的历史条件及特点?

《关于建国以来党的若干历史问题的决议》

关于斯巴达的论述错误的是()。

诸侯国的国君如何用人呢?有人主张：“左右皆曰不可，勿听；诸大夫皆曰不可，勿听；国人皆曰不可，然后察之，见不可焉，然后去之。”这种主张最终可能出自下列哪位思想家之口()。

“瓜步之战”发生在下列哪两个政权之间?()

巴黎和会召开的时间是()。

明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。

一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2

某系统有R1、R2和R3共3种资源，在TO时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况如表4-4所示，此时系统的可用资源向量为(2，1，2)。试问：将系统中各种资源总数和此刻各进程对各资源的需求个数用向量或矩阵表示出来。

为什么要实施融合战略?其实施的因素与条件是什么?

《千金方》中主治蓄血证的方剂是《内外伤辨惑论》中的半夏白术天麻汤源于

医学伦理学的指导原则有

关于混合式招标，下列说法错误的是()。

在前期物业管理期间，物业管理公司提供的服务，既包含物业正常使用期间的常规性服务，也包括()等前期物业管理的特殊内容。

产生遗嘱继承法律关系的法律事实是()

有关系R(A，B，C）和关系S(A，D，E，F)。如果将关系代数表达式πR.A.R.B.S.D.S.F(RS)用SQL的查询语句来表示，则有：SELECTR.A，R.B，S.D，S.FFROMR，SWHERE【】。

【B1】【B15】

Themanageratoncelosthis______whenhelearntthathissecretarywaslateagainforthemeeting.

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