首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图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-04-28
83
问题
设有向无环图G以邻接矩阵的方式存储,G
[j]中存放的是从结点i出发到结点j的边权,G
[j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。
给出算法的基本设计思想。
选项
答案
基本设计思想:我们知道可以利用弗洛伊德算法(floyd)来求得图中任意两点间的最短路径长度,这里的边权是正数,如果图中所有的边权均为负数,那我们根据弗洛伊德算法求出的便是任意两点间最小的负权路径长度,此时若把所有的边权取相反数,则刚才求得的最短路径长度的相反数一定是现在的最长路径长度;根据此思想,将图G的边权改为它的相反数,得到图G’,然后用floyd算法对G’求出每对顶点间的最短路径,那么图G.中最短路径的相反数即为原图G的最长路径长度。
解析
转载请注明原文地址:https://kaotiyun.com/show/1WRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
【奥地利王位继承战争】南京大学2013年国际关系史真题
1895年发现X射线,拉开物理学革命序幕的科学家是()。
拜占庭建筑风格的典型代表圣索菲亚大教堂建于()。
洋务派创办军事工业的方式是()。
在1875年宪法中关于法国立法权的叙述,不正确的是()。
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
“钟鸣鼎食”往往用来形容贵族生活。考古发现的青铜乐器“钟”始见于周代遗址,可能存在于()
二战后世界经济走向统一的过程中,仍然存在着多样性,出现了“两种体系、三种国家”,下列不属于社会主义国家经济类型的是()。
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
随机试题
风湿热的发病机制中下列哪项是不恰当的
28岁,初孕妇,妊娠39周,肋下有块状物,子宫呈纵椭圆形,胎先露部较软且不规则,胎心在脐上偏左
根据我国增值税法的规定,增值税的征税范围包括:()。
统一拆迁是由掌握拆迁政策、法规及具备拆迁技术的拆迁人,实施本单位建设项目的房屋拆迁工作。()
事业单位购入的固定资产,其成本包括购买价款、相关税费以及固定资产交付使用前所发生的可归属于该项资产的运输费、装卸费、安装调试费和专业人员服务费。()
某企业2016年利润总额为300万元,当年为开发新产品发生的研发费用为50万元(未形成无形资产,计入当期损益)。假设除此之外无其他纳税调整事项,税法规定研发费用可实行加计扣除政策,已知企业所得税税率为25%。则该企业2016年应缴纳企业所得税()
期望效应说明()
哲学基本问题的第一方面即物质和精神何者为第一性问题是()。
OffersWe’llrefund3XthedifferenceWithournewPRICEWATCHpromiseonselecteditemsweaimtoofferthe
A、Itwillbringherpotentialintofullplay.B、Itwillinvolvelotsoftraintravel.C、ItwillenablehertoimproveherChines
最新回复
(
0
)