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

admin2017-11-20 23

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

战国初期，上党地区在下列哪一个国家的控制范围之内?()
古代两河流域最具代表性的文学作品是()。
拜占庭建筑风格的典型代表圣索菲亚大教堂建于()。
中华人民共和国恢复了在联合国合法席位的时间是()。
近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。
建立帝国财政收支总账和元首金库，直接控制和调节全国财政收支的是()。
中古时代实行索贡巡行赋税征收方式的国家是()。
阅读史料，回答以下问题：重庆中央党部，暨中央执监委员诸同志均鉴：今年4月，临时全国代表大会宣言，说明此次抗战之原因，曰：“自塘沽协定以来，吾人所以忍辱负重与倭国周旋，无非欲停止军事行动，采用和平方法，先谋北方各省之保全，再进而谋东北四省问题之合
阅读史料回答以下问题：天既哀大地生人之多艰，黑帝乃降精而救民患，为神明，为圣王，为万世作师，为万民作保，为大地教主。生于乱世，乃据乱世而立三世之法，而垂精太平。乃因其所生之国，而立三世之义，而注意于大地远近、大小若一之大一统。乃立元以统天，以天为
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令，平均每条指令需要5个机器周期，其中3个周期必须访问内存，内存读写需一个机器周期，假定CPU在95％的时间内持续执行“背景程序”，且这段时间内不执行I／O指令。现

随机试题

Everybodywastouched______wordsaftertheyheardhermovingstory.
(2004年第49题)下列符合心电图诊断窦性停搏的是
A、实体觉检查B、两点辨别觉检查C、皮肤定位觉检查D、震动觉检查E、运动觉检查被检者闭目，检查者轻轻夹住被检者的手指或足趾两侧，上下移动5°左右，令被检者说出“向上”或“向下”
下列关于微囊的叙述错误的是()
企业交纳的下列税金中,可以不通过“应交税金”科目核算的是()。
我国采用定牌生产出口商品时，在商品或其包装上只能使用买方指定的商标或品牌，而不能注明“中国制造”字样。()
趋势线被突破后，这说明()。
(2013年单选8)马克思指出：立法者应该把自己看作一个自然科学家。对此，下列理解正确的是()。
求I=cos(x+y)|dxdy，其中D={(x，y)|0≤x≤，0≤y≤}．
We’llvisitEuropenextyearprovidedwehaveenoughmoney.

最新回复(0)

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

计算机408

学硕统考专业

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

古代两河流域最具代表性的文学作品是()。

拜占庭建筑风格的典型代表圣索菲亚大教堂建于()。

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

近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。

建立帝国财政收支总账和元首金库，直接控制和调节全国财政收支的是()。

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

Everybodywastouched______wordsaftertheyheardhermovingstory.

(2004年第49题)下列符合心电图诊断窦性停搏的是

A、实体觉检查B、两点辨别觉检查C、皮肤定位觉检查D、震动觉检查E、运动觉检查被检者闭目，检查者轻轻夹住被检者的手指或足趾两侧，上下移动5°左右，令被检者说出“向上”或“向下”

下列关于微囊的叙述错误的是()

企业交纳的下列税金中,可以不通过“应交税金”科目核算的是()。

我国采用定牌生产出口商品时，在商品或其包装上只能使用买方指定的商标或品牌，而不能注明“中国制造”字样。()

趋势线被突破后，这说明()。

(2013年单选8)马克思指出：立法者应该把自己看作一个自然科学家。对此，下列理解正确的是()。

求I=cos(x+y)|dxdy，其中D={(x，y)|0≤x≤，0≤y≤}．

We’llvisitEuropenextyearprovidedwehaveenoughmoney.

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