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

admin2017-04-28 60

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

选项

答案基本设计思想：我们知道可以利用弗洛伊德算法(floyd)来求得图中任意两点间的最短路径长度，这里的边权是正数，如果图中所有的边权均为负数，那我们根据弗洛伊德算法求出的便是任意两点间最小的负权路径长度，此时若把所有的边权取相反数，则刚才求得的最短路径长度的相反数一定是现在的最长路径长度；根据此思想，将图G的边权改为它的相反数，得到图G’，然后用floyd算法对G’求出每对顶点间的最短路径，那么图G．中最短路径的相反数即为原图G的最长路径长度。

解析

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

试以英国为例分析工业革命的深远影响。

【奥地利王位继承战争】南京大学2013年国际关系史真题

康有为在他的《孔子改制考》中将孔子奉为主张变革的先驱，下列描述正确的是()

胡适与李大钊进行“问题与主义之争”的主战场是()。

在夏文化的探索中，()最具有代表性。

在欧盟发展历史上，促使欧盟正式成立的文件是()。

1920年，苏俄农民中流传着这样的说法：“土地属于我们，面包却属于你们；水属于我们，鱼却属于你们；森林属于我们，木材却属于你们”，它反映的是战时共产主义政策()。

UNIX系统中，输入／输出设备看作是()。

随着时间的延长，钢材内部性质略有改变，称为时效，俗称“老化”。“时效”的后果是()。

根据项目后评价报告基本格式，“报告正文”提纲应包括()。

下列关于投资项目经济评价中盈亏平衡分析的说法，正确的是()

和谐社会是中国共产党领导下全体人民共建共享的社会。()

你单位要进行一次全市食品安全检查工作。如果让你做一个工作计划，你怎么做?

A、 B、 C、 D、 C观察给出的每一组图案，均分别由三个独立的小图构成，符合这一规律的只有C。

从教育科学的某一理论或一般性陈述出发推出新结论，推论出某特定假设。这种假设属于()

Ithasbeenjustlysaidthatwhile"wespeakwithourvocalorganswe(1)_____withourwholebodies".Allofuscommunicatewit

ToAmericans,politeconversationalistsempathizebydisplayingexpressionsofexcitementordisgust,shockorsadness.(Passage

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

计算机408

学硕统考专业

试以英国为例分析工业革命的深远影响。

【奥地利王位继承战争】南京大学2013年国际关系史真题

康有为在他的《孔子改制考》中将孔子奉为主张变革的先驱，下列描述正确的是()

胡适与李大钊进行“问题与主义之争”的主战场是()。

在夏文化的探索中，()最具有代表性。

在欧盟发展历史上，促使欧盟正式成立的文件是()。

1920年，苏俄农民中流传着这样的说法：“土地属于我们，面包却属于你们；水属于我们，鱼却属于你们；森林属于我们，木材却属于你们”，它反映的是战时共产主义政策()。

UNIX系统中，输入／输出设备看作是()。

随着时间的延长，钢材内部性质略有改变，称为时效，俗称“老化”。“时效”的后果是()。

根据项目后评价报告基本格式，“报告正文”提纲应包括()。

下列关于投资项目经济评价中盈亏平衡分析的说法，正确的是()

和谐社会是中国共产党领导下全体人民共建共享的社会。()

你单位要进行一次全市食品安全检查工作。如果让你做一个工作计划，你怎么做?

A、 B、 C、 D、 C观察给出的每一组图案，均分别由三个独立的小图构成，符合这一规律的只有C。

从教育科学的某一理论或一般性陈述出发推出新结论，推论出某特定假设。这种假设属于()

Ithasbeenjustlysaidthatwhile"wespeakwithourvocalorganswe(1)_____withourwholebodies".Allofuscommunicatewit

ToAmericans,politeconversationalistsempathizebydisplayingexpressionsofexcitementordisgust,shockorsadness.(Passage

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