首页 > 代码库 > 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算法的原理和实现