参考:https://baike.baidu.com/item/Floyd%E7%AE%97%E6%B3%95/291990
算法过程:
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直接相连。
时间复杂度与空间复杂度
时间复杂度:\(O(n^3)\)
空间复杂度:\(O(n^2)\)
优缺点分析:
Floyd算法适用于APSP(All Pairs Shortest Paths,多源最短路径),是一种动态规划算法,稠密图效果最佳,边权可正可负。此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次Dijkstra算法,也要高于执行|V|次SPFA算法。
优点:容易理解,可以算出任意两个节点之间的最短距离,代码编写简单。
缺点:时间复杂度比较高,不适合计算大量数据。
算法描述:
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即为所有点对的最短路径矩阵
【代码】
#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); }