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

来源:软件水平考试    发布时间:2012-11-05    软件水平考试视频    评论

  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<

视频学习

我考网版权与免责声明

① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;

② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。

最近更新

社区交流

考试问答