设有向无环图G以邻接矩阵的方式存储,G[i][j]中存放的是从结点i出发到结点j的边权,G[i][j]=0代表从i到j没有直接的边,试编写程序,求G图中最长的路径长度。 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。

admin2017-11-20  28

问题 设有向无环图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
0

最新回复(0)