首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图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
47
问题
设有向无环图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
学硕统考专业
相关试题推荐
下列关于古日耳曼人的社会状况的叙述中,不正确的是()。
为加强君权,皇太极时代开始直接控制的“上三旗”不包括()。
第一国际成立前,各国无产阶级强烈要求加强国际团结的直接原因是()。
科学技术革命包括三个既有联系又有区别的过程,下列不属于三个过程的是()。
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
中华人民共和国恢复在联合国合法席位的时间是()。
以下不属于对满族祖先的表述的是()。
两汉时期,下列没有通过丝绸之路传入西方的技术是()。
下列哪两个国家是第二次工业革命的发源地和“中心”?
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
随机试题
54岁,男性,胃大部切除术后出现顽固性呃逆,首先考虑
影响尿液渗透压的主要因素是
天然胆汁酸属于
指定会计科目就是指定出纳专管的科目。指定科目后,才能执行出纳签字,也才能查看现金或银行存款日记账。()
海关确定该批设备的完税价格时,应该采用的方法是()。如果该外商独资企业对完税价格审定的结果有异议,该企业可以采取的措施有()。
价外费用是向()收取的手续费。
下列关于经常项目外汇收支管理的表述中正确的是()。
某航空公司为增值税一般纳税人,2015年7月取得的含税收入包括航空培训收入57.72万元、航空摄影收入222.6万元、湿租业务收入199.8万元、干租业务收入245.7万元。该公司计算的下列增值税销项税额,正确的有()。
23,25,29,30,31,35,37,40,()
秘鲁附近海岸所属的自然带为:
最新回复
(
0
)