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

admin2017-04-28 40

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

选项

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

解析

转载请注明原文地址:https://jikaoti.com/ti/qIfjFFFM

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

简述美苏争霸的三个阶段，并分析其影响与教训。

《关于建国以来党的若干历史问题的决议》

光绪元年七月，清政府迫于()强烈要求派一位使臣到其国，()成为中国第一个驻外公使

关于东晋末年农民起义的表述中，不正确的是()

隋朝建立了三省六部制，其中负责审议的部门是()。

北约和华约两个组织对峙近半个世纪，其影响是()。

加尔文教传播到法国后，其信仰者被称为()。

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。

从下面关于虚拟设备的论述中，选择一条正确的论述()。

关于LH对男性的作用，下列说法正确的是：

陈独秀在《吾人最后之觉悟》一文中，将明清以来的中外文化第二次大交汇的历程分为()

Thethievesfledwiththelocalpolicecloseontheir______.

虚劳的治疗原则为

对于以信息为主要资源的房地产经纪行业，其管理的特点主要表现在应注重()。

路基填筑时，土质种类多，出现异类土壤混填，尤其是透水性差的土壤包裹透水性好的土壤，形成了水囊，容易造成的路基病害是()。

人耳对声音大小的感觉，近似地与声压呈()关系。

根据支付结算法律制度的规定，下列款项不可以转人个人人民币银行结算账户的是()。

下列情形中，按“利息、股息、红利所得”缴纳个人所得税的有()。

AcrisisatBancoEspiritoSanto(BES),oneofPortugal’sbiggestbanks,promptedaplungeinPortugal’sstockmarketandlesser

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

计算机408

学硕统考专业

简述美苏争霸的三个阶段，并分析其影响与教训。

《关于建国以来党的若干历史问题的决议》

光绪元年七月，清政府迫于()强烈要求派一位使臣到其国，()成为中国第一个驻外公使

关于东晋末年农民起义的表述中，不正确的是()

隋朝建立了三省六部制，其中负责审议的部门是()。

北约和华约两个组织对峙近半个世纪，其影响是()。

加尔文教传播到法国后，其信仰者被称为()。

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。

从下面关于虚拟设备的论述中，选择一条正确的论述()。

关于LH对男性的作用，下列说法正确的是：

陈独秀在《吾人最后之觉悟》一文中，将明清以来的中外文化第二次大交汇的历程分为()

Thethievesfledwiththelocalpolicecloseontheir______.

虚劳的治疗原则为

对于以信息为主要资源的房地产经纪行业，其管理的特点主要表现在应注重()。

路基填筑时，土质种类多，出现异类土壤混填，尤其是透水性差的土壤包裹透水性好的土壤，形成了水囊，容易造成的路基病害是()。

人耳对声音大小的感觉，近似地与声压呈()关系。

根据支付结算法律制度的规定，下列款项不可以转人个人人民币银行结算账户的是()。

下列情形中，按“利息、股息、红利所得”缴纳个人所得税的有()。

AcrisisatBancoEspiritoSanto(BES),oneofPortugal’sbiggestbanks,promptedaplungeinPortugal’sstockmarketandlesser

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