数据结构笔记分享——弗洛伊德（ Floy
所有顶点之间的最短路径，本来可以重复使用迪杰斯特拉（Djikstra）算法，但是时间复杂度就是O(n^3)所以一般使用弗洛伊德算法文章来源：C++技术原创文章版权所有，未经授权，禁止转载。
弗洛伊德算法的基本思想是：设集合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++实现
templateclassTvoidExtMGraphT::Floyd(T**d,int**path){ inti,j,k; for(i=0;in;i++) for(j=0;jn;j++){ d[i][j]=a[i][j]; if(i!=ja[i][j]INFTY)path[i][j]=i;elsepath[i][j]=-1; }for(k=0;kn;k++)for(i=0;in;i++)for(j=0;jn;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的“当前最短路径”的长度。
文章来源：C++技术原创文章版权所有，未经授权，禁止转载。
北京有治白癜风的专业医院吗北京治疗白癜风的费用要多少钱