当前位置:C++技术网 > 资讯 > 数据结构笔记分享:23 弗洛伊德( Floyd)算法

数据结构笔记分享:23 弗洛伊德( Floyd)算法

更新时间:2015-12-09 20:33:33浏览次数:1+次

   弗洛伊德算法的基本思想是:设集合S的初始状态为空集合。然后依此向集合S中加入顶点0,1,…,n-1,每次加入一个顶点。

   在算法执行中,d[i][j]被定义为:从i到j中间只经过S中的顶点的,所有可能的路径中的最短路径的长度。如果从i到j,中间只经过S中的顶点当前没有路径相通,那么d[i][j]为一个大值MaxNum。不妨称此时的d[i][j]中保存的是从i到j的“当前最短路径”的长度。


数据结构

集合S:

    加入顶点v0,v1,…,vn-1,每次加入一个顶点。

二维数组d

   d[i][j]: 从vi到vj的“当前最短路径”的长度。

   dk[i][j] :从vi到vj,中间允许经过的顶点的编号不大于k的情况下的当前最短路径的长度。

二维数组path

    path[i][j]给出从vi到vj的最短路径上顶点vj前面的那个顶点若从v0到v2的最短路径为(v0,v1,v3,v2)则有path[0][2]=3,path[0][3]=1,path[0][1]=0

c++实现

template<class T>
void ExtMGraph<T>::Floyd(T **d, int **path)
{
	  int i,j,k;
	  for(i=0;i<n;i++)
	     for (j=0;j<n;j++){
		    d[i][j]=a[i][j];   
		    if (i!=j && a[i][j]<INFTY) path[i][j]=i;
            else path[i][j]=-1;
	     }
    for (k=0;k<n;k++) 
        for (i=0;i<n;i++)
           for (j=0;j<n;j++) 
               if (d[i][k]+d[k][j] < d[i][j] ){
                   d[i][j]=d[i][k]+d[k][j];
	                  path[i][j]=path[k][j];
		       }
}

时间分析

   容易看出,弗洛伊德算法的时间复杂度为O(n3),与通过n次调用迪杰斯特拉算法来计算图中所有顶点间的最短路径的做法具有相同的时间复杂度。但如果实际需要计算图中任意两个顶点间的最短路径时,弗洛伊德算法显然比迪杰斯特拉算法简洁。

   弗洛伊德算法的基本思想是:设集合S的初始状态为空集合。然后依此向集合S中加入顶点0,1,…,n-1,每次加入一个顶点。

   在算法执行中,d[i][j]被定义为:从i到j中间只经过S中的顶点的,所有可能的路径中的最短路径的长度。如果从i到j,中间只经过S中的顶点当前没 有路径相通,那么d[i][j]为一个大值MaxNum。不妨称此时的d[i][j]中保存的是从i到j的“当前最短路径”的长度。