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-11-20  78
问题 设有向无环图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://www.kaotiyun.com/show/oNRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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