首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图G以邻接矩阵的方式存储,G[i][j]中存放的是从结点i出发到结点j的边权,G[i][j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。 给出算法的基本设计思想。
设有向无环图G以邻接矩阵的方式存储,G[i][j]中存放的是从结点i出发到结点j的边权,G[i][j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。 给出算法的基本设计思想。
admin
2017-11-20
83
问题
设有向无环图G以邻接矩阵的方式存储,G
[j]中存放的是从结点i出发到结点j的边权,G
[j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。
给出算法的基本设计思想。
选项
答案
基本设计思想:我们知道可以利用弗洛伊德算法(floyd)来求得图中任意两点间的最短路径长度,这里的边权是正数,如果图中所有的边权均为负数,那我们根据弗洛伊德算法求出的便是任意两点间最小的负权路径长度,此时若把所有的边权取相反数,则刚才求得的最短路径长度的相反数一定是现在的最长路径长度;根据此思想,将图G的边权改为它的相反数,得到图G’,然后用floyd算法对G’求出每对顶点间的最短路径,那么图G’中最短路径的相反数即为原图G的最长路径长度。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/ENRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
《齐民要求.序》中写道:“今采摭经传,爰及歌谣,洵之老成,验之行事,起自农耕,终于醯醢(酱醋),资生之靡不毕书书;号日《齐民要术》……舍本逐末,贤哲所非……故商贾之事,阙而不录。”这段材料表明作者()。①采取古今资料的编撰原则②
在巴黎和会上获利最大的两个国家是()。
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
解放军渡江战役中横渡长江的东西两个攻击点是()。
詹天佑自主设计修建了中国第一条铁路是在()。
在巴黎和会上,法国要求严厉制裁德国的目的是()。
试析第三次科学技术革命对人类社会和历史进程的影响。
在罗斯福新政期间,美国政府在森林中修筑铁路,力图为美国青年人提供更多的工作机会。这种举措有利于()。①缓和阶级矛盾和安定社会秩序②扩大消费,刺激经济复苏③根除资本主义经济危机④消除资本主义社会的基本矛盾
随机试题
中国革命必须走农村包围城市的道路,其主要依据是()
A.Osier结B.Ewart征C.肝脏扩张性搏动D.Duroziez氏血管杂音E.Beck三联征
患者,女,32岁,不慎外阴受伤,20分钟后出现外阴肿物,疼痛难忍,最可能的诊断是
下列哪项不是甘草的粉末特征( )。
在国际债券市场上,不需要官方主管机构批准,也不受货币发行国有关法令管制和约束的债券是()。
一般认为,金融工具具有流动性、风险性和收益性的特征。()
禁止与取缔,是指公安机关依法对某些犯罪行为和违反治安管理、扰乱社会秩序、妨害公共安全的行为宣布禁止,予以取缔,并对违禁者予以法律制裁。( )
自顶向下规划的重要目标是达到信息的一致性,即保证下列()的一致。Ⅰ.数字字段定义Ⅱ.数据结构Ⅲ.更新时间Ⅳ.更新规划Ⅴ.数据记录
将内部专用IP地址转换为外部公用IP地址的技术是()。
若有以下程序段intr=8;printf("%d\n",r>>1);输出结果是
最新回复
(
0
)