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

admin2017-11-20 72

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

近代英国思想家洛克的代表作是
元朝各行政区的行政机构称为()。()有指挥军事活动的权力，遇有征伐则设置()。
下列关于国际联盟及其活动的叙述，正确的是()。
新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。
第一国际成立前，各国无产阶级强烈要求加强国际团结的直接原因是()。
19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。
我国生铁冶炼技术最早出现于()。
全国高校院系调整的具体时间是()。
假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量
若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。

随机试题

社会主义在曲折中持续发展是不可扭转的趋势，因为社会主义制度能够从根本上克服生产资料的资本主义私有制对生产力发展的束缚。社会主义能够在改革中不断实现自我发展和自我完善。社会主义改革根源于社会主义社会的基本矛盾。生产力与生产关系之间、经济基础和上层建筑之间在相
雌激素的生理作用有
A、补益肺肾，纳气平喘B、益气回阳，救阴固脱C、清肺豁痰，补肾固脱D、扶阳固脱，镇摄肾气D考点为正虚喘脱证：喘逆剧甚，张口抬肩，鼻扇气促，端坐不能平卧，稍动则咳喘欲绝，或有痰鸣，心慌动悸，烦躁不安，面青唇紫，汗出如珠，肢冷，脉浮大无根，或见歇止，或
某公司2009年的销售收入为3000万元，应收账款为300万元，则该公司2009年度的应收账款周转天数为()天。
(2007年考试真题)在下列各项中，属于财务管理经济环境构成要素的有()。
长江公司系甲公司的母公司，2×17年6月30日，长江公司向甲公司销售一件产品，销售价格为1000万元，增值税税额为170万元，账面价值为900万元，相关款项已收存银行。甲公司将购入的该产品作为管理用固定资产(增值税进项税额可抵扣)核算，并于当日投入使用，预
我国的民族自治制度优越性主要体现在哪几个方面?()
已知x+=3，则x4+的值为()
鼠标器与主机的接口有多种，下面哪一种接口不会用作鼠标器与主机的接口?
Thelostscarfdescription.①Asquaresilkscarf②Color:(5)③Size:(6)feetsquare④Price:(7)dollar⑤T

最新回复(0)

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

计算机408

学硕统考专业

近代英国思想家洛克的代表作是

元朝各行政区的行政机构称为()。()有指挥军事活动的权力，遇有征伐则设置()。

下列关于国际联盟及其活动的叙述，正确的是()。

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

第一国际成立前，各国无产阶级强烈要求加强国际团结的直接原因是()。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

我国生铁冶炼技术最早出现于()。

全国高校院系调整的具体时间是()。

假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量

若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。

雌激素的生理作用有

某公司2009年的销售收入为3000万元，应收账款为300万元，则该公司2009年度的应收账款周转天数为()天。

(2007年考试真题)在下列各项中，属于财务管理经济环境构成要素的有()。

我国的民族自治制度优越性主要体现在哪几个方面?()

已知x+=3，则x4+的值为()

鼠标器与主机的接口有多种，下面哪一种接口不会用作鼠标器与主机的接口?

Thelostscarfdescription.①Asquaresilkscarf②Color:(5)③Size:(6)feetsquare④Price:(7)dollar⑤T

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