电话:0731-83595998
导航

2011年软考程序员考试复习笔试知识点整理(13)

来源: 2017-10-20 14:14

 17、求任意两个节点之间最短距离--Floyd算法

  Floyd算法:给出一个图(通常可以在任何图中使用,包括有向图、带负权边的图),求最短路径问题的一个O(n^3)算法。

  优点:容易理解,可以算出任意两个节点之间最短距离的算法,程序容易写;

  缺点:复杂度达到三次方,不适合计算大量数据;

  它需要用邻接矩阵来储存边,这个算法通过考虑最佳子路径来得到最佳路径。注意单独一条边的路径也不一定是最佳路径。

  Floyd-Warshall算法的基本思路是:

  1.用d[i][j]记录每对顶点间的最短距离;

  2.对每一个图中的顶点,以其作为基点扫描每一对d[i][j],检验是否通过该基点可以使得这对顶点间的距离变小。

  //dist(i,j) 为从节点i到节点j的最短距离

  Fori←1 to n do

  For j←1 to n do

  dist(i,j) = weight(i,j)

  Fork←1 to n do // k为"媒介节点"

  For i←1 to n do

  For j←1 to n do

  if (dist(i,k) + dist(k,j) < dist(i,j))then // 是否是更短的路径?

  dist(i,j) = dist(i,k) + dist(k,j)

  我们实际是很容易就可以写出这个算法的代码:

  #defineN 100

  voidFloyd(int dist[N][N],int n)

  {

  int i,j,k;

  for(k=0;k

  for(i=0;i

  for(j=0;j

  if(dist[i][k]+dist[k][j]

  dist[i][j]=dist[i][k]+dist[k][j];

  }

  即使问题是求单源最短路径,还是推荐使用这个算法,如果时间和空间允许的话(只要有放的下邻接矩阵的空间,时间上就没问题)。

  对上面的代码来说,我们还面临一个保存路径的问题,如何来做呢?

  /*多源最短路径floyd_warshall算法*/

  #defineN 100

  intmap[N][N];

  voidFloyd(int dist[N][N],int path[N][N],int n)

  {

  int i,j,k;

  for(i=0;i

  for(j=0;j

  dist[i][j]=map[i][j], path[i][j]=0;

  for(k=0;k

  for(i=0;i

  for(j=0;j

  if(dist[i][k]+dist[k][j]

  {

  dist[i][j]=dist[i][k]+dist[k][j];

  path[i][j]=k;

  }

  }

  voidoutput(int i,int j)

  {

  if(i==j)

  return;

  if(path[i][j]==0)

  cout

编辑推荐:

下载Word文档

温馨提示:因考试政策、内容不断变化与调整,长理培训网站提供的以上信息仅供参考,如有异议,请考生以权威部门公布的内容为准! (责任编辑:长理培训)

网络课程 新人注册送三重礼

已有 22658 名学员学习以下课程通过考试

网友评论(共0条评论)

请自觉遵守互联网相关政策法规,评论内容只代表网友观点!

最新评论

点击加载更多评论>>

精品课程

更多
10781人学习

免费试听更多

相关推荐
图书更多+
  • 电网书籍
  • 财会书籍
  • 其它工学书籍
拼团课程更多+
  • 电气拼团课程
  • 财会拼团课程
  • 其它工学拼团
热门排行

长理培训客户端 资讯,试题,视频一手掌握

去 App Store 免费下载 iOS 客户端