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

admin2017-11-20 27

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

关于德国工业革命，说法不正确的是()。
西汉初年，西域共有36国，其中以()人口最多。
在西北地区，西北野战军采取了蘑菇战术与敌人周旋，这实际上是()。
中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》，强调要()。
在1875年宪法中关于法国立法权的叙述，不正确的是()。
中古时代实行索贡巡行赋税征收方式的国家是()。
阅读材料，回答以下问题：重庆中央党部，暨中央执监委员诸同志均鉴：今年4月，临时全国代表大会宣言，说明此次抗战之原因，曰：“自塘沽协定以来，吾人所以忍辱负重与倭国周旋，无非欲停止军事行动，采用和平方法，先谋北方各省之保全，再进而谋东北四省问题之合理解决，
印加人记载事物使用的方法是()。
三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时，就拒绝分配资源，但是，银行家算法要求的条件并不是必要的。例如，某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下：(1)请说明系统处于不安全状态；(2

随机试题

风险权重为()的资产，包括对国家投资的公共企业的债权。
对直径8～10mm的普通圆钢进行焊接，不适宜的焊接方法是(　　)焊。
某企业年初所有者权益总额160万元，当年以其中的资本公积转增资本50万元。当年实现净利润300万元，提取盈余公积30万元，向投资者分配利润20万元。该企业年末所有者权益总额为()万元。
经营者能够证明所达成的协议属于一定条件的，可被《反垄断法》豁免，这些情况包括()。
认识的客体是指主体实践和认识活动的对象。()
交警刘某在某区设点检查时，发现一辆私家车辆途经此地并停车下客。经向乘车人员倪某、陆某询问，轿车司机张某和倪某、陆某谈妥了目的地、车费15元后同意两人搭乘，检查时，尚未收取车费。调查期间，刘某多次打断张某的申辩，对其说：“你就不要狡辩了，现在证据确凿。”后刘
自由贸易指国家对进出口贸易不加任何限制和干涉，允许商品自由输出和输入，在国内外市场上进行自由竞争的一种对外贸易政策。根据上述定义，下列属于自由贸易的是：
品德发展的实质是什么?
StoneHillMallisdifferentfromothermallsbecauseithasWhatmakesStoneHillMallamorefavourableshoppingplaceis
A、Japanesepeopleeatmorepickledvegetables.B、Japanesepeopleeatmoredairy.C、Japanesepeopleeatmorefish.D、Japanesepeo

最新回复(0)

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

计算机408

学硕统考专业

关于德国工业革命，说法不正确的是()。

西汉初年，西域共有36国，其中以()人口最多。

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

中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》，强调要()。

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

中古时代实行索贡巡行赋税征收方式的国家是()。

印加人记载事物使用的方法是()。

三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

风险权重为()的资产，包括对国家投资的公共企业的债权。

对直径8～10mm的普通圆钢进行焊接，不适宜的焊接方法是( )焊。

某企业年初所有者权益总额160万元，当年以其中的资本公积转增资本50万元。当年实现净利润300万元，提取盈余公积30万元，向投资者分配利润20万元。该企业年末所有者权益总额为()万元。

经营者能够证明所达成的协议属于一定条件的，可被《反垄断法》豁免，这些情况包括()。

认识的客体是指主体实践和认识活动的对象。()

自由贸易指国家对进出口贸易不加任何限制和干涉，允许商品自由输出和输入，在国内外市场上进行自由竞争的一种对外贸易政策。根据上述定义，下列属于自由贸易的是：

品德发展的实质是什么?

StoneHillMallisdifferentfromothermallsbecauseithasWhatmakesStoneHillMallamorefavourableshoppingplaceis

A、Japanesepeopleeatmorepickledvegetables.B、Japanesepeopleeatmoredairy.C、Japanesepeopleeatmorefish.D、Japanesepeo

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

对直径8～10mm的普通圆钢进行焊接，不适宜的焊接方法是(　　)焊。