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

admin2017-04-28 57

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

结合诸条约内容简述中国社会沦为半殖民地半封建社会的过程。
论述第二次鸦片战争的结局对中国社会有什么影响。
资本主义生产关系萌芽是怎样产生和发展的?给明清社会带来什么样的影响?
以下不是巴黎和会的主要议题的是()
阅读材料，回答问题：材料一：战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金，如美国时发展原子能工业的投资，从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场，从50年代中期起，为加强国际市场的竞争力，政府
以下()协议完成了从网卡到IP地址的映射。
以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的语句是()。
在TELNET协议中，用户发送的命令采用TCP传输到服务器，在TCP的数据包中，需要把()符号位置移位，从而使服务器尽快响应命令。
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
某系统有R1、R2和R3共3种资源，在TO时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况如表4-4所示，此时系统的可用资源向量为(2，1，2)。试问：如果此时P1和P2均发出资源请求向量Request(1，0，1)，为了保证系统的安全性，应

随机试题

Whatwillthelistenersprobablydothen?
CPU与存储器之间在速度的匹配方面存在着矛盾，一般采用多级存储系统层次结构来解决或缓和矛盾。按速度的快慢排列，它们是高速缓存、内存、_________。
幽门梗阻时禁用下列哪类药物
肩周炎的最主要治疗方法是
小柴胡汤和蒿芩清胆汤中均含有药物是
承担产品侵权责任的要件包括()。
市人民检察院对于王某涉嫌非法向外国人出售、赠送珍贵文物罪，应当如何处理？指控王某犯有巨额财产来源不明罪，首先应当承担证明其财产或者支出明显超过合法收入且差额巨大的证明责任的，是下列选项中的哪些机关或人员？
（）是指对具有估计性的会计事项，应当谨慎从事，应当合理预计可能发生的损失和费用，不预计或少预计可能带来的利润。
将Fe、Mg合金4．00g投入到足量的一定浓度的硝酸中，金属与硝酸完全反应(金属全部溶解)，共收集到标准状况下的气体VL(气体为No租NO2)，若向反应后的溶液中加入足量的氢氧化钠溶液，理论上最多可得沉淀8．25g，则V值可能为()。
方程x＋2＝ex根的个数是[]．

最新回复(0)

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

计算机408

学硕统考专业

结合诸条约内容简述中国社会沦为半殖民地半封建社会的过程。

论述第二次鸦片战争的结局对中国社会有什么影响。

资本主义生产关系萌芽是怎样产生和发展的?给明清社会带来什么样的影响?

以下不是巴黎和会的主要议题的是()

以下()协议完成了从网卡到IP地址的映射。

以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的语句是()。

在TELNET协议中，用户发送的命令采用TCP传输到服务器，在TCP的数据包中，需要把()符号位置移位，从而使服务器尽快响应命令。

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

某系统有R1、R2和R3共3种资源，在TO时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况如表4-4所示，此时系统的可用资源向量为(2，1，2)。试问：如果此时P1和P2均发出资源请求向量Request(1，0，1)，为了保证系统的安全性，应

Whatwillthelistenersprobablydothen?

CPU与存储器之间在速度的匹配方面存在着矛盾，一般采用多级存储系统层次结构来解决或缓和矛盾。按速度的快慢排列，它们是高速缓存、内存、_________。

幽门梗阻时禁用下列哪类药物

肩周炎的最主要治疗方法是

小柴胡汤和蒿芩清胆汤中均含有药物是

承担产品侵权责任的要件包括()。

（）是指对具有估计性的会计事项，应当谨慎从事，应当合理预计可能发生的损失和费用，不预计或少预计可能带来的利润。

将Fe、Mg合金4．00g投入到足量的一定浓度的硝酸中，金属与硝酸完全反应(金属全部溶解)，共收集到标准状况下的气体VL(气体为No租NO2)，若向反应后的溶液中加入足量的氢氧化钠溶液，理论上最多可得沉淀8．25g，则V值可能为()。

方程x＋2＝ex根的个数是[]．

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