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

admin2017-04-28 63

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

古埃及中王国时期出现了一个新兴的手工业部门，对世界文明做出了巨大贡献。这一新兴的手工业部门是()。

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

下列关于1929～1933年经济危机的描述，错误的有()。

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

“两个凡是”

明朝中叶，美洲高产的农作物()的传入，对改变当时人们的食品结构产生了重大影响。

编写判定给定的二叉树是否是二叉排序树的函数。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

熔池的一次结晶包括_和_两个过程。

人类基因组

患儿，女，16岁。于右膝下有一肿块，5年来逐渐增大，无痛，步态正常。X线摄片发现右胫骨内上方有一肿物，基底部有骨小梁与胫骨相连，顶盖部致密度减低，边界尚可辨认。根据以上证候，最可能的诊断是

化脓性肺炎最常见的细菌感染为

A．胁肋胀痛，游走不定B．胁肋刺痛，痛有定处C．胁肋隐痛，其痛不休D．胁痛口苦，脘腹痞闷E．右上腹痛，暖气泛酸肝气郁结胁痛的主症之一是

浮小麦具有的功效是()

某宗房地产的收益年限为无限年，预计其未来第一年的总收益和总费用分别为30万元和8万元，此后每年的总收益和总费用在上一年的基础上增加2％，该类房地产的资本化率为10％，则该宗房地产的收益价格为275万元。()

可以直接在水泥基层上涂刷，耐洗刷性好，能用于潮气较大的部位的建筑内墙涂料是()。

下列观点错误的有()。

访谈法的优点不包括()。

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

计算机408

学硕统考专业

古埃及中王国时期出现了一个新兴的手工业部门，对世界文明做出了巨大贡献。这一新兴的手工业部门是()。

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

下列关于1929～1933年经济危机的描述，错误的有()。

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

“两个凡是”

明朝中叶，美洲高产的农作物()的传入，对改变当时人们的食品结构产生了重大影响。

编写判定给定的二叉树是否是二叉排序树的函数。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

熔池的一次结晶包括_______和_______两个过程。

人类基因组

患儿，女，16岁。于右膝下有一肿块，5年来逐渐增大，无痛，步态正常。X线摄片发现右胫骨内上方有一肿物，基底部有骨小梁与胫骨相连，顶盖部致密度减低，边界尚可辨认。根据以上证候，最可能的诊断是

化脓性肺炎最常见的细菌感染为

A．胁肋胀痛，游走不定B．胁肋刺痛，痛有定处C．胁肋隐痛，其痛不休D．胁痛口苦，脘腹痞闷E．右上腹痛，暖气泛酸肝气郁结胁痛的主症之一是

浮小麦具有的功效是()

某宗房地产的收益年限为无限年，预计其未来第一年的总收益和总费用分别为30万元和8万元，此后每年的总收益和总费用在上一年的基础上增加2％，该类房地产的资本化率为10％，则该宗房地产的收益价格为275万元。()

可以直接在水泥基层上涂刷，耐洗刷性好，能用于潮气较大的部位的建筑内墙涂料是()。

下列观点错误的有()。

访谈法的优点不包括()。

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

熔池的一次结晶包括_和_两个过程。