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

admin2017-11-20 52

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

在西北地区，西北野战军采取了蘑菇战术与敌人周旋，这实际上是()。
兵家是专门研究军事理论和实践的学派，主要代表人物是战国中期齐国的()，他所著的兵书是一部杰出的古代兵书。
1988年6月，苏联共产党第十九次代表会议的主题是()。
开皇五年，文帝规定每年正月五日县令出查，令百姓五党三党为一团，根据标准定户等上下，从轻制定税额，并将各户应纳税额写成定簿，是为()。
在阿拉伯()统治时期，阿拉伯军队曾与当时中国的唐朝军队发生冲突。
北约和华约两个组织对峙近半个世纪，其影响是()。
世界近代史上，世界经济发展经历了两次大的飞跃，即第一次工业革命和第二次工业革命。阅读下面两段材料，回答问题：材料一工业革命的主角——蒸汽机，是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产，主要依靠以人力和经
假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量
某虚拟存储系统中有一个进程共有6页(0～5)，其中代码占3页(0～2)，数据占1页(3)，数据堆占1页(4)，用户栈占1页(5)。它们依次存放在外存的22，23，25，26存储块。当前，代码页已经分配在物理内存的66，67，87页，数据页为31，并已经进行

随机试题

简述五种谈判战略。
将函数f(x)=在x=0处展成幂级数，并指明收敛区间．
以下哪项是独活寄生汤中的组成药物
对不伤害原则的解释，正确的是
(2006年）世界各国都将公共秩序保留作为捍卫本国根本利益的一项重要法律制度。关于这一制度，下列哪项判断是错误的?（）
私有房屋出租人必须持有(),承租人必须持有()。
()限额对多头头寸和空头头寸相抵后的净额加以限制。
注册会计师应关注期中获取的审计证据的相关性和可靠性能否合理地延伸至期末。以下审计程序中，属于专为证实这种合理延伸而实施的审计程序有()。
打折：促销：竞争()
在Word2003中，关于嵌入式对象，下列说法错误的是()。

最新回复(0)

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

计算机408

学硕统考专业

在西北地区，西北野战军采取了蘑菇战术与敌人周旋，这实际上是()。

兵家是专门研究军事理论和实践的学派，主要代表人物是战国中期齐国的()，他所著的兵书是一部杰出的古代兵书。

1988年6月，苏联共产党第十九次代表会议的主题是()。

开皇五年，文帝规定每年正月五日县令出查，令百姓五党三党为一团，根据标准定户等上下，从轻制定税额，并将各户应纳税额写成定簿，是为()。

在阿拉伯()统治时期，阿拉伯军队曾与当时中国的唐朝军队发生冲突。

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

假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量

简述五种谈判战略。

将函数f(x)=在x=0处展成幂级数，并指明收敛区间．

以下哪项是独活寄生汤中的组成药物

对不伤害原则的解释，正确的是

(2006年）世界各国都将公共秩序保留作为捍卫本国根本利益的一项重要法律制度。关于这一制度，下列哪项判断是错误的?（）

私有房屋出租人必须持有(),承租人必须持有()。

()限额对多头头寸和空头头寸相抵后的净额加以限制。

注册会计师应关注期中获取的审计证据的相关性和可靠性能否合理地延伸至期末。以下审计程序中，属于专为证实这种合理延伸而实施的审计程序有()。

打折：促销：竞争()

在Word2003中，关于嵌入式对象，下列说法错误的是()。

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