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

admin2017-11-20 42

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

战国初期，上党地区在下列哪一个国家的控制范围之内?()
古埃及中王国时期出现了一个新兴的手工业部门，对世界文明做出了巨大贡献。这一新兴的手工业部门是()。
下列选项中，对东汉度田问题的描述中，不正确的是()
中华人民共和国恢复在联合国合法席位的时间是()。
阅读材料，回答以下问题：第四章总统第二十九条临时大总统、副总统由参议院选举之。以总员四分之三以上出席，得票满投票总数三分之二以上者为当选。第三十条临时大总统代表临时政府，总揽政务，公布法律。第三十一条临时大总统为执行法律或基于法
1945年，联合国成立之时，创始会员国共有()个国家。
设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。
三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev
某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。
某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下：假定int类型数据用32位补码表示，程序

随机试题

Themanagerneedsanassistantthathecan______totakecareofproblemsinhisabsence.
对于交通性气胸患者，采用胸腔闭式引流治疗时，错误的说法是
下列哪项中，不是可摘局部义齿塑料基托的优点
下列哪些场所应设消防备用泵()。
下列各项中，不符合消费税纳税义务发生时间规定的有()。
根据《中华人民共和国劳动法》(以下简称《劳动法》)的规定，劳动合同可以约定试用期，但试用期最长不得超过()。
我国现阶段以团队方式开展出国旅游，团队的人数至少为()。
()发展了一种对自我概念定性测量的方法——“我是谁”。
王之涣《凉州词》中出现了一种中国古老的民族乐器是()。
"MoneyMattersonCampus"isarecentlyreleasedstudyonfinancialliteracyamongyoungadults.Itsupportsprovidingstudents

最新回复(0)

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

计算机408

学硕统考专业

战国初期，上党地区在下列哪一个国家的控制范围之内?()

古埃及中王国时期出现了一个新兴的手工业部门，对世界文明做出了巨大贡献。这一新兴的手工业部门是()。

下列选项中，对东汉度田问题的描述中，不正确的是()

中华人民共和国恢复在联合国合法席位的时间是()。

1945年，联合国成立之时，创始会员国共有()个国家。

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

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

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

Themanagerneedsanassistantthathecan______totakecareofproblemsinhisabsence.

对于交通性气胸患者，采用胸腔闭式引流治疗时，错误的说法是

下列哪项中，不是可摘局部义齿塑料基托的优点

下列哪些场所应设消防备用泵()。

下列各项中，不符合消费税纳税义务发生时间规定的有()。

根据《中华人民共和国劳动法》(以下简称《劳动法》)的规定，劳动合同可以约定试用期，但试用期最长不得超过()。

我国现阶段以团队方式开展出国旅游，团队的人数至少为()。

()发展了一种对自我概念定性测量的方法——“我是谁”。

王之涣《凉州词》中出现了一种中国古老的民族乐器是()。

"MoneyMattersonCampus"isarecentlyreleasedstudyonfinancialliteracyamongyoungadults.Itsupportsprovidingstudents

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