首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图G以邻接矩阵的方式存储，G[i][j]中存放的是从结点i出发到结点j的边权，G[i][j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。 给出算法的时间复杂度。
设有向无环图G以邻接矩阵的方式存储，G[i][j]中存放的是从结点i出发到结点j的边权，G[i][j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。 给出算法的时间复杂度。
admin
2017-11-20
65
问题
设有向无环图G以邻接矩阵的方式存储，G
[j]中存放的是从结点i出发到结点j的边权，G
[j]=0代表从i到j没有直接的边，试编写程序，求G图中最长的路径长度。
给出算法的时间复杂度。
选项
答案
时间复杂度分析：因为用到了floyd算法，而遍历新图用到的是两层循环(小于O(n
3
))，故时间复杂度为O(n
3
)(n代表节点的个数)。
解析
转载请注明原文地址:https://kaotiyun.com/show/sNRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
十六国时期的历史，可以划分为前后两个时期，其分界线是()。
毛泽东认为，社会主义这个阶段可分为两个阶段，包括()。
中华人民共和国恢复了在联合国合法席位的时间是()。
1950年2月14日，周恩来代表中国与苏联签订的条约是()。
在捍卫和传播生物进化论方面做出了贡献的是()。
下列关于俄国十月革命和德国十一月革命共同点的表述，不正确的是()。
以下不属于对满族祖先的表述的是()。
林则徐主持编译的《四洲志》，介绍了世界各国的史地。鸦片战争后，主要以《四洲志》为基础成书的重要著作是()
1945年，联合国成立之时，创始会员国共有()个国家。
某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下：假定int类型数据用32位补码表示，程序
随机试题
子宫内膜增生症的病理特点、病因及发病机制。
“心藏脉，脉舍神”主要说明了：()
患者4岁，因外伤左上乳中切牙内陷移位，牙龈无明显撕裂伤，牙槽突无折断，X线片显示恒牙胚未受波及。正确的处理是
女性，38岁，糖尿病12年，每日皮下注射人混合胰岛素治疗，早餐前30U，晚餐前24U，每日进餐规律，主食量300g。近来空腹血糖12．5mmol／L，餐后血糖7．6～9．0mmol／L。最可能的情况是
初三学生王洋经常迟到、旷课、上游戏厅，甚至打架、敲竹杠，尽管老师多次教育，仍不见好转，以致班主任老师对他失去了信心。该教师的这种做法，不符合教师道德规范中的()。
“学会如何学习”实质上是指()。
17，28，19，26，21，24，()，22。
试论网络时代的受众变化。(清华大学2007研)
根据《宪法》相关规定，下列关于非公有制经济的表述，错误的是()
循环队列的存储空间为Q(1：50)，初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又正常地插入了一个元素，则循环队列中的元个数为()。
最新回复
(
0
)
