来自百度百科
Floyd算法
弗洛伊德算法一般指Floyd算法 <dl class="basicInfo-block basicInfo-left"> <dt class="basicInfo-item name"> 中文名 </dt> <dd class="basicInfo-item value"> 弗洛伊德算法 </dd> <dt class="basicInfo-item name"> 外文名 </dt> <dd class="basicInfo-item value"> Floyd(Floyd-Warshall) </dd> </dl> <dl class="basicInfo-block basicInfo-right"> <dt class="basicInfo-item name"> 时间复杂度 </dt> <dd class="basicInfo-item value"> O(n^3) </dd> <dt class="basicInfo-item name"> 空间复杂度 </dt> <dd class="basicInfo-item value"> O(n^2) </dd> <dt class="basicInfo-item name"> 作 用 </dt> <dd class="basicInfo-item value"> 求多源最短路径,求传递闭包 </dd> </dl>
目录
Floyd算法核心思路
编辑Floyd算法路径矩阵
从图的带权 邻接矩阵A=[a(i,j)] n×n开始, 递归地进行n次更新,即由矩阵D(0)=A,按一个公式,构造出矩阵D(1);又用同样地公式由D(1)构造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,称D(n)为图的 距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用松弛技术( 松弛操作),对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);
Floyd算法状态转移方程
其 状态转移方程如下: map[i,j]:=min{map[i,k]+map[k,j],map[i,j]};
map[i,j]表示i到j的最短距离,K是穷举 i,j的断点,map[n,n]初值应该为0,或者按照题目意思来做。
当然,如果这条路没有通的话,还必须特殊处理,比如没有map[i,k]这条路。
Floyd算法算法过程
编辑 1,从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。
2,对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[i][j]=d,d表示该路的长度;否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息,D[i][j]表示从Vi到Vj需要经过的点,初始化D[i][j]=j。把各个顶点插入图中,比较插点后的距离与原来的距离,G[i][j] = min( G[i][j], G[i][k]+G[k][j] ),如果G[i][j]的值变小,则D[i][j]=k。在G中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息。
比如,要寻找从V5到V1的路径。根据D,假如D(5,1)=3则说明从V5到V1经过V3,路径为{V5,V3,V1},如果D(5,3)=3,说明V5与V3直接相连,如果D(3,1)=1,说明V3与V1直接相连。
Floyd算法时间复杂度与空间复杂度
编辑 时间复杂度:O(n^3);
空间复杂度:O(n^2) [1]
Floyd算法优缺点分析
编辑 Floyd算法适用于APSP(All Pairs Shortest Paths,多源最短路径),是一种动态规划算法,稠密图效果最佳,边权可正可负。此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次 Dijkstra算法,也要高于执行|V|次 SPFA算法。
优点:容易理解,可以算出任意两个节点之间的最短距离,代码编写简单。
缺点:时间复杂度比较高,不适合计算大量数据。
Floyd算法算法描述
编辑 a) 初始化:D[u,v]=A[u,v]
b) For k:=1 to n
For i:=1 to n
For j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then
D[i,j]:=D[i,k]+D[k,j];
c) 算法结束:D即为所有点对的最短路径矩阵
Floyd算法参考代码
编辑Floyd算法C语言
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include<stdio.h> #include<stdlib.h> #define max 1000000000 int d[1000][1000],path[1000][1000]; int main() { int i,j,k,m,n; int x,y,z; scanf ( "%d%d" ,&n,&m); for (i=1;i<=n;i++) for (j=1;j<=n;j++){ d[i][j]=max; path[i][j]=j; } for (i=1;i<=m;i++) { scanf ( "%d%d%d" ,&x,&y,&z); d[x][y]=z; d[y][x]=z; } for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;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[i][k]; } } for (i=1;i<=n;i++) for (j=1;j<=i;j++) if (i!=j) printf ( "%d->%d:%d\n" ,i,j,d[i][j]); int f, en; scanf ( "%d%d" ,&f,&en); while (f!=en) { printf ( "%d->" ,f); f=path[f][en]; } printf ( "%d\n" ,en); return 0; } |
Floyd算法C++语言
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include<iostream> #include<vector> using namespace std; const int &INF=100000000; void floyd(vector<vector< int > > &distmap, //可被更新的邻接矩阵,更新后不能确定原有边 vector<vector< int > > &path) //路径上到达该点的中转点 //福利:这个函数没有用除INF外的任何全局量,可以直接复制! { const int &NODE=distmap.size(); //用邻接矩阵的大小传递顶点个数,减少参数传递 path.assign(NODE,vector< int >(NODE,-1)); //初始化路径数组 for ( int k=1; k!=NODE; ++k) //对于每一个中转点 for ( int i=0; i!=NODE; ++i) //枚举源点 for ( int j=0; j!=NODE; ++j) //枚举终点 if (distmap[i][j]>distmap[i][k]+distmap[k][j]) //不满足三角不等式 { distmap[i][j]=distmap[i][k]+distmap[k][j]; //更新 path[i][j]=k; //记录路径 } } void print( const int &beg, const int &end, const vector<vector< int > > &path) //传引用,避免拷贝,不占用内存空间 //也可以用栈结构先进后出的特性来代替函数递归 { if (path[beg][end]>=0) { print(beg,path[beg][end],path); print(path[beg][end],end,path); } else cout<< "->" <<end; } int main() { int n_num,e_num,beg,end; //含义见下 cout<< "(不处理负权回路)输入点数、边数:" ; cin>>n_num>>e_num; vector<vector< int > > path, distmap(n_num,vector< int >(n_num,INF)); //默认初始化邻接矩阵 for ( int i=0,p,q; i!=e_num; ++i) { cout<< "输入第" <<i+1<< "条边的起点、终点、长度(100000000代表无穷大,不联通):" ; cin>>p>>q; cin>>distmap[p][q]; } floyd(distmap,path); cout<< "计算完毕,可以开始查询,请输入出发点和终点:" ; cin>>beg>>end; cout<< "最短距离为" <<distmap[beg][end]<< ",打印路径:" <<beg; print(beg,end,path); } |