2. 考研
  3. 设有向无环图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++语言描述算法，关键之处给出注释。

admin2017-04-28  87
问题 设有向无环图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

学硕统考专业

相关试题推荐
随机试题
最新回复(0)