首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有向无环图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-04-28
81
问题
设有向无环图G以邻接矩阵的方式存储,G
[j]中存放的是从结点i出发到结点j的边权,G
[j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。
根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
选项
答案
算法实现如下: int floyd (Graph G) { //构造一个新图 int dist[n](nl; //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][kl+distfk][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++) int floyd (Graph G) { //构造一个新图 int dist[n](nl; //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 ;=0;j <G.G.VerticeNum(),j++) if (dist[i][j]>dist [i][kl+distfk][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/2WRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下面哪部经典是我国最早的官方史书?()
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
洋务派创办军事工业的方式是()。
30年代,美国政府对一系列国际问题执行中立政策,最主要的原因是()。
下列哪个文件标志着“文化大革命”的发起?()
1543年发表解剖学专著《人体结构论》的是()。
(1)根据无类IP地址的规则,每个网段中有两个地址是不分配的:主机号全0表示网络地址,主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2,即254台。该网络要划分为两个子网,每个子网要120台主机,因此主机位数X应该满足下面三个条件:
某公司的局域网设置如下所示,两个局域网通过路由器连接到NAT、服务器上,并且通过NAT服务器连接到Internet上。局域网1的掩码是192.168.14.0/25,局域网2的掩码是192.168.14.128/25,NAT服务器的内部IP地址为192.1
下列选项中,降低进程优先级的合理时机是____。
假定某计算机的CPU主频为80MHz,CPI为4,并且平均每条指令访存1.5次,主存与cache之间交换的块大小为16B,Caehe的命中率为99%,存储器总线宽度为32位。请回答下列问题。CPU和DMA控制器同时要求使用存储器总线时,哪个优先级更高?
随机试题
A青霉素B红霉素C阿米卡星D利巴韦林E头孢菌素肺炎链球菌肺炎选用
桂枝汤中具有调和营卫作用的配伍是()
A.5%B.7%~8%C.10%D.25%~30%E.50%~60%婴儿基础代谢所需能量占总能量的
A.吉林B.河北C.云南D.福建E.安徽三七的主产地是()。
下列关于法律与社会关系的说法中,正确的是?
某期房预计两年后竣工交付使用,目前与其类似的现房价格为4500元/m2,出租的年末净收益为500元/m2。假设年折现率为8%,风险补偿估计为现房价格的3%,则该期房目前的价格为()。[2007年考题]
租赁设备的窝工费,一般按()计算。
在其他教育基本要素都具备的情况下,在教育过程中起决定作用的是()
下列操作中,不属于Applet安全限制的是( )。
以下正确的字符串常量是()。
最新回复
(
0
)