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

admin2017-04-28 32

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

“灌木林原野事件”
汉章帝会群儒于白虎观，讨论经义，由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书，这部书系统地吸收了阴阳五行和谶纬之学，形成今文经学派的主要观点。
1988年6月，苏联共产党第十九次代表会议的主题是()。
宁夏回族自治区的设立时间是()。
美国主张建立国际联盟的主要目的是()。
阅读材料，回答问题：材料一：战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金，如美国时发展原子能工业的投资，从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场，从50年代中期起，为加强国际市场的竞争力，政府
1141年，金与南宋双方签订协议，规定以淮水和大散关为宋金的分界线，此协议称为（）。
三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev
相对于单一内核结构，采用微内核结构设计实现操作系统具有诸多好处，但是，()并不是微内核的优势。
某计算机字长为16位，主存地址空间大小为128KB，按字编址。采用单字长指令格式，指令各字段定义如图B-4所示。转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义见表B-1。请回答下列问题：转移指令的目标地址范围是多少?

随机试题

下列饮片的原植物不以干燥根茎为入药部位的是
再生障碍性贫血的骨髓表现主要是
A．国家工商行政管理部门B．国家卫生计生部门C．国家发展和改革宏观调控部门D．国家工业和信息化部门负责药品价格的监督管理工作的部门是
工业生产过程中粉尘危害的控制措施有()。
timeofshipment
如图所示为一个支架，竖直固定杆BC的上端C安装一个定滑轮，轻杆OA水平，O为铰链，重物G悬挂在A点。现将一根轻绳跨过定滑轮，一端固定在A端，另一端施加水平拉力F使OA逆时针缓慢旋转，不计一切摩擦，则下列说法正确的是()。
[*]
乘客与火车票间的联系类型是什么?将ER图转换为关系模式，并指出主码。
【B1】【B8】
A、Lessmoneywillbespentinmaintainingthehouse.B、Theymaysavesomemoneyforthetimebeing.C、Sheishappywiththepric

最新回复(0)

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

计算机408

学硕统考专业

“灌木林原野事件”

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

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

宁夏回族自治区的设立时间是()。

美国主张建立国际联盟的主要目的是()。

1141年，金与南宋双方签订协议，规定以淮水和大散关为宋金的分界线，此协议称为（）。

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

相对于单一内核结构，采用微内核结构设计实现操作系统具有诸多好处，但是，()并不是微内核的优势。

下列饮片的原植物不以干燥根茎为入药部位的是

再生障碍性贫血的骨髓表现主要是

A．国家工商行政管理部门B．国家卫生计生部门C．国家发展和改革宏观调控部门D．国家工业和信息化部门负责药品价格的监督管理工作的部门是

工业生产过程中粉尘危害的控制措施有()。

timeofshipment

[*]

乘客与火车票间的联系类型是什么?将ER图转换为关系模式，并指出主码。

【B1】【B8】

A、Lessmoneywillbespentinmaintainingthehouse.B、Theymaysavesomemoneyforthetimebeing.C、Sheishappywiththepric

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