首页 > 代码库 > Floyd算法的原理和实现
Floyd算法的原理和实现
一.算法介绍
Floyd算法是一种在有向图中求最短路径的算法。相比不能再有向图中包含负权值的dijkstra算法,Floyd算法可以用在拥有负权值的有向图中求解最短路径(不过不能包含负权回路)。它是一种求解有向图中点与点之间最短路径的算法。
我们检查有向图中的每一个节点X,对于图中过的2点A和B,如果有Dis(AX)+Dis(XB)<Dis(AB),那么使得Dis(AB)=Dis(AX)+Dis(XB)。当所有的节点X遍历完后,AB的最短路径就求出来了。
所以,核心代码很简单,其中N是顶点个数,时间复杂度为O(N^3)
其中要注意3个for循环的嵌套顺序
void floyd(int N) { int i,j,k; for(k=0;k<N;k++) { for(i=0;i<N;i++) { for(j=0;j<N;j++) { if(Dis[i][k]+Dis[k][j]<Dis[i][j]) { Dis[i][j]=Dis[i][k]+Dis[k][j]; } } } } }二.算法的原理
Floyd算法原理是一种动态规划的思想。
设Ak(i,j)表示从i点到j点索引号不大于K的最短路径,
则求出最短路径,可表示为
for(K=0;K<N;K++)
然后依次求A0(i,j), A1(i,j), ..., An(i,j) ,其中A0(i,j)表示初始化时候的图
在这个过程中,我们要先求A0(i,j)才能求A1(i,j),再求A2(i,j).....所以这是一种自底向上的设计思想,为什么要先求A0(i,j)才能求A1(i,j),再求A2(i,j)呢.....
因为算法的运行过程是这样的。
我们可以由Ak(i,j)求出Ak-1(i,j),那么对于Ak(i,j)来说,无外乎2种情况
第一种:
Ak(i,j)不经过点k,此时
Ak(i,j)=Ak-1(i,j)
因为对于索引号不经过k的2个点i,j,竟然经过k了,那么就应该在索引号不大于K-1里面找最短路径了
第二种:
Ak(i,j)经过了点k,此时
Ak(i,j)=Ak-1(i,k)+Ak-1(i,k)
因为经过了k,所以此时路径分2部分,一部分是从i到k,另外一部分是k,到j,因为k此时已经作为了2部分路径的起点或者终点,所以此时要求这2部分的最短路径时,就是使用Ak-1(i,k)和Ak-1(i,k)。这是一种DP的思想。
那么2种情况我最后肯定是选路径断的那一条,
所以Ak(i,j) = min( Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j) )
这一步其实就对应了代码部分的:
if(Dis[i][k]+Dis[k][j]<Dis[i][j]) { Dis[i][j]=Dis[i][k]+Dis[k][j]; }三:打印路径
用path[i][j]纪录路径信息。
假设我们存在路径1→5→7→9,那么先求path[1][9]=7,再求path[1][7]=5,再求path[1][5]=1。
所以,算法应该改为,其中加入path[i][j]=k,因为当路径更新,该路径进过了k点,所以要纪录下来
void floyd(int N) { int i,j,k; for(k=0;k<N;k++) { for(i=0;i<N;i++) { for(j=0;j<N;j++) { if(Dis[i][k]+Dis[k][j]<Dis[i][j]) { Dis[i][j]=Dis[i][k]+Dis[k][j]; path[i][j]=k; } } } } }path[i][j]初始化代码:
一开始我们假设图的任意2点都是连接的
for(i=0;i<N;i++) { for(j=0;j<N;j++) { path[i][j]=i; } }四:源码
该代码用邻接矩阵存储图,输入1000表示2个顶点不可达(权值无限大)
#include<iostream> #include<stack> using namespace std; #define MAX 1000 int Graph[MAX][MAX]; int Dis[MAX][MAX]; #define infinite 1000 int path[MAX][MAX]; void floyd(int N) { int i,j,k; for(k=0;k<N;k++) { for(i=0;i<N;i++) { for(j=0;j<N;j++) { if(Dis[i][k]+Dis[k][j]<Dis[i][j]) { Dis[i][j]=Dis[i][k]+Dis[k][j]; path[i][j]=k; } } } } } void print_path(int N) { int i,j; for(i=0;i<N;i++) { for(j=0;j<N;j++) { if((i!=j) &&Dis[i][j]!=infinite) { cout<<i+1<<"----"<<j+1<<" distance:"<<Dis[i][j]<<endl; cout<<"path:"<<endl; int k=j; stack <int> ph; do { k=path[i][k]; ph.push(k); }while(k!=i); cout<<ph.top()+1; ph.pop(); while(!ph.empty()) { cout<<"->"<<ph.top()+1; ph.pop(); } cout<<"->"<<j+1<<endl; } } } } void main() { int N,i,j; cin>>N; for(i=0;i<N;i++) { for(j=0;j<N;j++) { int g; cin>>g; Graph[i][j]=g; Dis[i][j]=g; } } //初始化路径 for(i=0;i<N;i++) { for(j=0;j<N;j++) { path[i][j]=i; } } floyd(N); print_path(N); system("pause"); }
测试用的图:
测试结果:
Floyd算法的原理和实现