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

admin2017-04-28 57

问题设有向无环图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

学硕统考专业

论述中国封建社会中后期赋税制度变迁的主要内容。

试述君士坦丁堡的陷落过程及其影响。

试述宋代理学产业的社会背景及主要内容。

兵家是专门研究军事理论和实践的学派，主要代表人物是战国中期齐国的()，他所著的兵书是一部杰出的古代兵书。

开皇五年，文帝规定每年正月五日县令出查，令百姓五党三党为一团，根据标准定户等上下，从轻制定税额，并将各户应纳税额写成定簿，是为()。

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

二次大战后，主要资本主义国家经历了增长时期，首先开始这个进程的国家是()。

Therewereathousandreasonsnottostop.Iwasrunninglateforaveryimportant...well,whateveritwasthatIwasrunning

血浆总磷脂中含量最多的是

最早应用的移植是

企业采用重置成本、可变现净值、现值和公允价值计量的，应当保证所确定的会计要素金额能够取得并可靠计量。()

根据以下资料，回答以下题。2013年10月份，社会消费品零售总额21491亿元，同比名义增长13．3％。其中，限额以上企业(单位)消费品零售额10579亿元，增长12．4％。1～10月份，社会消费品零售总额190308亿元，同比增长13．0％。按经

Vi8ualFoxPro0的项目文件的扩展名是______。

有如下语句序列：Dima，bAsIntegerPrintaPrintb执行以上语句序列，下列叙述中错误的是

Oneafternoon,whenthelessonswereover,JohnandMikeGreendidn’tgohome.They(11)inschooltohelptheirteacher.The

Itmaycomeasasurprisetomanyanexhaustedmotherorfather—butthinkingaboutyourchildrencouldimproveyourmemory,ast

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

计算机408

学硕统考专业

论述中国封建社会中后期赋税制度变迁的主要内容。

试述君士坦丁堡的陷落过程及其影响。

试述宋代理学产业的社会背景及主要内容。

兵家是专门研究军事理论和实践的学派，主要代表人物是战国中期齐国的()，他所著的兵书是一部杰出的古代兵书。

开皇五年，文帝规定每年正月五日县令出查，令百姓五党三党为一团，根据标准定户等上下，从轻制定税额，并将各户应纳税额写成定簿，是为()。

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

二次大战后，主要资本主义国家经历了增长时期，首先开始这个进程的国家是()。

Therewereathousandreasonsnottostop.Iwasrunninglateforaveryimportant...well,whateveritwasthatIwasrunning

血浆总磷脂中含量最多的是

最早应用的移植是

企业采用重置成本、可变现净值、现值和公允价值计量的，应当保证所确定的会计要素金额能够取得并可靠计量。()

Vi8ualFoxPro0的项目文件的扩展名是______。

有如下语句序列：Dima，bAsIntegerPrintaPrintb执行以上语句序列，下列叙述中错误的是

Oneafternoon,whenthelessonswereover,JohnandMikeGreendidn’tgohome.They(11)inschooltohelptheirteacher.The

Itmaycomeasasurprisetomanyanexhaustedmotherorfather—butthinkingaboutyourchildrencouldimproveyourmemory,ast

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