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

admin2017-11-20 30

问题设有向无环图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题库学硕统考专业分类

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

1948年3月，英国、法国、比利时、荷兰、卢森堡5国缔结了5国《合作和集体防御条约》，即()，这是一项以军事同盟为核心的包括政治、经济、文化的合作条约。

有人说：“我们应当以资本供给全世界，而谁以资本供给全世界，谁就应当管理全世界。”讲这话的应该是()。

1950年2月14日，周恩来代表中国与苏联签订的条约是()。

在夏文化的探索中，()最具有代表性。

二战以来，资本主义经济在发展中出现了许多新问题，这主要表现在()

关于垄断组织的积极作用，不正确的说法是()。

二战期间，下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役

下列有关西欧封建社会的表述，错误的一项是()。

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

调节机体功能活动的系统是()

内旋转发生的位置是

枳实导滞丸作用力强，其君药是()。

下列合同或凭证中，应缴纳印花税的有()。(2014年)

如果员工的能力完全超出了工作的要求，那么会()。

西洋铜管乐器，音色嘹亮辉煌，善于表现雄壮有力的音乐情绪，还能吹奏优美如歌的旋律的乐器是()。

Societiesallovertheworldnameplacesinsimilarways.Quiteoftenthereisnoofficialnamingceremonybutplacestendtobe

下列用来比喻“没有依靠，无处投奔的人”的是：

Ifanation’sinterestratesarerelativelylowcomparedtothoseofothercountries,thentheexchangevalueofitscurrencywi

Peopleappeartobeborntocompute.Thenumericalskillsofchildrendevelopsoearlyandsoinexorably(坚定地)thatitiseasyt

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

计算机408

学硕统考专业

1948年3月，英国、法国、比利时、荷兰、卢森堡5国缔结了5国《合作和集体防御条约》，即()，这是一项以军事同盟为核心的包括政治、经济、文化的合作条约。

有人说：“我们应当以资本供给全世界，而谁以资本供给全世界，谁就应当管理全世界。”讲这话的应该是()。

1950年2月14日，周恩来代表中国与苏联签订的条约是()。

在夏文化的探索中，()最具有代表性。

二战以来，资本主义经济在发展中出现了许多新问题，这主要表现在()

关于垄断组织的积极作用，不正确的说法是()。

二战期间，下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役

下列有关西欧封建社会的表述，错误的一项是()。

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

调节机体功能活动的系统是()

内旋转发生的位置是

枳实导滞丸作用力强，其君药是()。

下列合同或凭证中，应缴纳印花税的有()。(2014年)

如果员工的能力完全超出了工作的要求，那么会()。

西洋铜管乐器，音色嘹亮辉煌，善于表现雄壮有力的音乐情绪，还能吹奏优美如歌的旋律的乐器是()。

Societiesallovertheworldnameplacesinsimilarways.Quiteoftenthereisnoofficialnamingceremonybutplacestendtobe

下列用来比喻“没有依靠，无处投奔的人”的是：

Ifanation’sinterestratesarerelativelylowcomparedtothoseofothercountries,thentheexchangevalueofitscurrencywi

Peopleappeartobeborntocompute.Thenumericalskillsofchildrendevelopsoearlyandsoinexorably(坚定地)thatitiseasyt

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