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

 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