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

admin2017-11-20 33

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

选项

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

解析

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

1988年起，苏联民族矛盾激化，民族分离运动加剧，第二次较大规模的民族冲突是()。

下列关于古日耳曼人的社会状况的叙述中，不正确的是()。

1925年爆发的当时世界上罢工时间最长的一次斗争是()。

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

下面有关兵制的内容，与唐玄宗有关的是()

中国共产党在敌后战场上开创的第一块根据地是()。

以孙中山为首的革命派和以康有为代表的维新派，是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()

印度种姓制度中，处于被剥削被压迫地位的两个瓦尔那是()①婆罗门②刹帝利③首陀罗④吠舍

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

常用的16Mn钢是牌号为()的低合金高强度钢。

中风，邪入经的典型症状是()

人们的理想信念存在于人们的内心深处，属于一种精神现象。但它又不只是一种纯粹的主观现象和静止的精神状态，而是一种包含着行动意志的复合现象，表现为从精神向行动的转变过程。这说明理想信念具有()

由肺炎链球菌引起的新生儿肺炎，治疗应首选

寒热往来是哪种病证的特征

A、声音嘶哑B、失声或严重的呼吸困难C、声调降低D、饮水呛咳E、低血钙喉上神经外支损伤时可出现

泵送混凝土中，宜加入()。

Inthelasteightyears,Concordiahas.FromConcordias’pointofview,theroleofcommunicationisto.

Heboughtherwhatshewanted,____thefactthattheywerecostly.

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

计算机408

学硕统考专业

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

1988年起，苏联民族矛盾激化，民族分离运动加剧，第二次较大规模的民族冲突是()。

下列关于古日耳曼人的社会状况的叙述中，不正确的是()。

1925年爆发的当时世界上罢工时间最长的一次斗争是()。

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

下面有关兵制的内容，与唐玄宗有关的是()

中国共产党在敌后战场上开创的第一块根据地是()。

以孙中山为首的革命派和以康有为代表的维新派，是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()

印度种姓制度中，处于被剥削被压迫地位的两个瓦尔那是()①婆罗门②刹帝利③首陀罗④吠舍

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

常用的16Mn钢是牌号为()的低合金高强度钢。

中风，邪入经的典型症状是()

人们的理想信念存在于人们的内心深处，属于一种精神现象。但它又不只是一种纯粹的主观现象和静止的精神状态，而是一种包含着行动意志的复合现象，表现为从精神向行动的转变过程。这说明理想信念具有()

由肺炎链球菌引起的新生儿肺炎，治疗应首选

寒热往来是哪种病证的特征

A、声音嘶哑B、失声或严重的呼吸困难C、声调降低D、饮水呛咳E、低血钙喉上神经外支损伤时可出现

泵送混凝土中，宜加入()。

Inthelasteightyears,Concordiahas______.FromConcordias’pointofview,theroleofcommunicationisto______.

Heboughtherwhatshewanted,____thefactthattheywerecostly.

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

Inthelasteightyears,Concordiahas.FromConcordias’pointofview,theroleofcommunicationisto.