首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图G以邻接矩阵的方式存储,G[i][j]中存放的是从结点i出发到结点j的边权,G[i][j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
设有向无环图G以邻接矩阵的方式存储,G[i][j]中存放的是从结点i出发到结点j的边权,G[i][j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
admin
2017-11-20
90
问题
设有向无环图G以邻接矩阵的方式存储,G
[j]中存放的是从结点i出发到结点j的边权,G
[j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。
根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
选项
答案
算法实现如下: int floyd(Graph G) { //构造一个新图 int dist[n][n]; //n是已经定义的常量,代表图中顶点的个数 for(int i=0;i<G.VerticeNum();i++) { for(int j=0;j<G.VerticeNum();j++) { dist[i][j]=-G.weight(i,j); //初始化新图的边权 } } //弗洛伊德算法 for (int k=0;k<G.G.VerticeNum();k++) { for(int i=0;i<G.G.VerticeNum();i++) for(int j=0;j<G.G.VerticeNum();j++) if(dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j]; } //遍历新图,找出最大路径长度 int max=0; for(int i=0;i<G.VerticeNum(),i++) for(int j=0;j<G.VerticeNum();j++) if(max<-dist[i][j]) max=-dist[i][j]; return max; }
解析
转载请注明原文地址:https://kaotiyun.com/show/oNRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
蒙古军西征之后,罗斯处于()的控制之下。
巴黎和会讨论的中心问题是()。
1988年6月,苏联共产党第十九次代表会议的主题是()。
下面哪项条约没有涉及德国的赔款问题?()
“瓜步之战”发生在下列哪两个政权之间?()
开皇五年,文帝规定每年正月五日县令出查,令百姓五党三党为一团,根据标准定户等上下,从轻制定税额,并将各户应纳税额写成定簿,是为()。
中国共产党在敌后战场上开创的第一块根据地是()。
印加人记载事物使用的方法是()。
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
随机试题
含A,B两种成分的混合液,只有当分配系数大于1时,才能用萃取操作进行分离。()
简述系统设计说明书的内容。
新生儿胎粪的特点是
女,34岁,持续性镜下血尿伴间断排尿不适3年,Hb120g/L,尿蛋白2g/24h,尿RBC20—30个/HP,WBC2~3个/HP,尿RBC位相示:正常20%,异常80%,下一步最主要的检查是
成人膀胱的容积是
尿沉渣镜检每高倍视野多少个白细胞即视为异常
患者,男,35岁。缺失3个月,要求固定修复。一般情况下,倾斜牙做基牙,其倾斜度不能超过
根据《建设工程安全生产管理条例》,不需要按照国家有关规定经过专门的安全作业培训,并取得特种作业操作资格证书后,方可上岗作业的人员是()。
听筝柳中庸抽弦促柱听秦筝,无限秦人悲怨声。似逐春风知柳态,如随啼鸟识花情。谁家独夜愁灯影?何处空楼思月明?更入几重离别恨,江南歧路洛阳城。诗人说“听筝”听出了“无限秦人悲怨声”,试分析诗中都有哪些“悲怨声”。
你被录用为基层的警察。请你谈谈应该如何做好工作。
最新回复
(
0
)