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

admin2017-04-28 54

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

1907年召开的第二国际斯图加特代表大会上，争论最激烈的问题是()。
(北魏孝文帝)“初谋南迁，恐众心恋旧，乃示为大举，因以胁定群情，外谋南伐，其实迁也。旧人怀土，多不所愿，内惮南征，无敢言者。于是定都洛阳。”上引材料不能说明的问题是()。
改革开放以来，乡镇企业的异军突起，其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径
在巴黎和会上，法国要求严厉制裁德国的目的是()。
下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界
以下()协议完成了从网卡到IP地址的映射。
假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量
在一个8级中断的系统中，硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8，通过中断屏蔽技术，将中断处理优先顺序设置为1→3→5→7→2→4→6→8，如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达，CPU在按优先顺序处理到第
下列的网络协议中，()的运输层协议是使用TCP的。
当系统发生抖动(thrashing)时，可以采取的有效措施是____。I．撤销部分进程Ⅱ．增加磁盘交换区的容量Ⅲ．提高用户进程的优先级

随机试题

活动和交往是学生思想品德形成和发展的基础，因此把学生置于活动和交往的环境中就必然会促进他们思想品质的形成和发展。()
巴黎圣母院的建筑风格属于【】
中水管道上不得装设()。
委托方()，税务师事务所可以在代理期限内单方终止代理行为。
()一般用于进出口贸易款项的收付，没有银行信用介入。
劳务派遣中，()属于用工单位应当履行的义务。[2015年5月二级真题]
隋唐至宋，在宫廷宴饮时娱乐欣赏的音乐称为()。
2018年A市进出口总额1.56亿美元，其中出口总额1.02亿美元，进口总额0.54亿美元。出口大于进口4765万美元。全年对美国出口590万美元，比上年下降24%；对香港地区出口260万美元，下降60%；对日本出口171
张军在一次羽毛球训练中不慎拉伤了手臂，要是在平常，这样的伤根本不算什么，但______________是在就要走上比武场的时候，这样的伤，______________让人揪心。填入画横线部分最恰当的一项是：
Therearesomeobjectsintheskythatmovesoquicklythatsometimesyouonlyseethemoutofthecornerofyoureye.Theseare

最新回复(0)

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

计算机408

学硕统考专业

1907年召开的第二国际斯图加特代表大会上，争论最激烈的问题是()。

(北魏孝文帝)“初谋南迁，恐众心恋旧，乃示为大举，因以胁定群情，外谋南伐，其实迁也。旧人怀土，多不所愿，内惮南征，无敢言者。于是定都洛阳。”上引材料不能说明的问题是()。

改革开放以来，乡镇企业的异军突起，其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径

在巴黎和会上，法国要求严厉制裁德国的目的是()。

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界

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

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

下列的网络协议中，()的运输层协议是使用TCP的。

当系统发生抖动(thrashing)时，可以采取的有效措施是____。I．撤销部分进程Ⅱ．增加磁盘交换区的容量Ⅲ．提高用户进程的优先级

活动和交往是学生思想品德形成和发展的基础，因此把学生置于活动和交往的环境中就必然会促进他们思想品质的形成和发展。()

巴黎圣母院的建筑风格属于【】

中水管道上不得装设()。

委托方()，税务师事务所可以在代理期限内单方终止代理行为。

()一般用于进出口贸易款项的收付，没有银行信用介入。

劳务派遣中，()属于用工单位应当履行的义务。[2015年5月二级真题]

隋唐至宋，在宫廷宴饮时娱乐欣赏的音乐称为()。

2018年A市进出口总额1.56亿美元，其中出口总额1.02亿美元，进口总额0.54亿美元。出口大于进口4765万美元。全年对美国出口590万美元，比上年下降24%；对香港地区出口260万美元，下降60%；对日本出口171

张军在一次羽毛球训练中不慎拉伤了手臂，要是在平常，这样的伤根本不算什么，但______________是在就要走上比武场的时候，这样的伤，______________让人揪心。填入画横线部分最恰当的一项是：

Therearesomeobjectsintheskythatmovesoquicklythatsometimesyouonlyseethemoutofthecornerofyoureye.Theseare

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

张军在一次羽毛球训练中不慎拉伤了手臂，要是在平常，这样的伤根本不算什么，但是在就要走上比武场的时候，这样的伤，让人揪心。填入画横线部分最恰当的一项是：