最短路径-Floyd

    之前我们接触学习了Dijkstra算法求解一个顶点到其他各个顶点的最短路径和距离，但如果我们想知道每一对顶点的最短路径和距离时，可以通过以每一个顶点作为源点循环求出每对顶点之间的最小距离。除此之外，我们可以利用本篇博客即将学习的弗洛伊德(Floyd）算法来求两顶点之间的最短距离。

弗洛伊德(Floyd)算法

 

1)算法思想原理：

 

      从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

 

2).算法描述：

 

a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 　　

 

b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

 

3）具体实现步骤

要操作的有向图如图所示：

用邻接矩阵表示为：

 

#define INF 99999 //表示不可到达

#define MAXSIZE 4 //表示图的结点数

//邻接矩阵存储图的信息
int map[MAXSIZE][MAXSIZE]={
	{0,5,INF,7},
	{INF,0,4,2},
	{3,3,0,2},
	{INF,INF,1,0}
};

 

 

定义

A[MAXSIZE][MAXSIZE]：   A[i][j]表示当前顶点i到j的最短距离

path[MAXSIZE][MAXSIZE]:   保存最短路径

 

Floyd算法过程矩阵的计算----十字交叉法

先初始化2个数组：

 

//数据初始化
	for(int i=0;i<MAXSIZE;i++)
	{
		for(int j=0;j<MAXSIZE;j++)
		{
			A[i][j]=map[i][j];
			path[i][j]=-1;//初始化为-1
		}
	}

 

 

即得到：

 1）使用十字交叉法，划去第0行和第0列以及左对角线，即

 

 

此时不在这三条线上的数据有：A[1][2]=4;A[1][3]=2;A[2][3]=2;A[2][1]=3等6个数。

此时根据A^k(i,j) = min( A^k-1(i,j), A^k-1(i,k) + A^k-1(k,j) )对比看是否要数据更新

例如看A[2][1]=3这个数是否要更新。

 

此时A[0][1]+A[2][0]=8>A[2][1]=3

所以不用更新，其他5和数都是这样判断，会发现都不用更新

 

 1）使用十字交叉法，划去第1行和第1列以及左对角线，即

 

此时不在这3条线上的数据依次是：A[0][2],A[0][3],A[2][0],A[2][3],A[3][0],A[3][2]

我们来看数据A[0][2]。

 
 

发现

A[0][2]>A[0][1]+A[1][2]=5+4=9(图中画出矩形顶点的和,即A[0][2]附近2个顶点的和，不是对角线那个顶点);

此时修改A[0][2]=9,path[0][2]=1(即划去的行号和列号,也是3条线交点的坐标）

按照此方法检查其他剩下的5个数，最后得到

 

以此类推。最后得到：

 

理解清楚步骤后，写出Floyd算法代码为：

 

//弗洛伊德算法
void Floyd()
{
	int path[MAXSIZE][MAXSIZE];//保存最短路径

	int A[MAXSIZE][MAXSIZE];//a[i][j]表示当前顶点i到j的最短距离

	//数据初始化
	for(int i=0;i<MAXSIZE;i++)
	{
		for(int j=0;j<MAXSIZE;j++)
		{
			A[i][j]=map[i][j];
			path[i][j]=-1;//初始化为-1
		}
	}

	for(int diagonal=0;diagonal<MAXSIZE;diagonal++)//左对角线
	{
		for(int k=0;k<MAXSIZE;k++)//行
		{
			if(k!=diagonal)//除去此行所有的点
				for(int j=0;j<MAXSIZE;j++)//列
				{
					 if(j!=diagonal)//除去此列所以的点
					 {
						 if(k!=j)//除去对角线的点
						 {
							 if(A[k][j]>A[diagonal][j]+A[k][diagonal])//满足条件
							 {
								 A[k][j]=A[diagonal][j]+A[k][diagonal];
								 path[k][j]=diagonal;
							 }
						 }
					 }
				}
		}
	}

}

 

得到A[MAXSIZE][MAXSIZE]和path[]数组后。

A[i][j]: 表示从顶点i到顶点j的最短距离。

 

而最短路径还要通过path[]数组计算得来。计算方法如下：

 

例如我们求解顶点3到顶点1的最小距离和路径：

 

最小距离：A[3][1]=4

最短路径：

path[3][1]=2;

path[2][1]=-1(一旦值为-1，停止计算）

所以顶点1前面经过的是顶点2，

即最后路径为：

3->2->1;

j结果显示代码为：

//结果输出：
	for(int i=0;i<MAXSIZE;i++)
	{
		for(int j=0;j<MAXSIZE;j++)
		{
			if(A[i][j]==INF)
				cout<<"从顶点"<<i<<"到顶点"<<j<<"不存在路径"<<endl;
			else
			{
				cout<<"从顶点"<<i<<"到顶点"<<j<<"最短距离为: "<<A[i][j]<<"  其路径为：";
				vector<int>temp;
				temp.insert(temp.begin(),j);//把终点插入
				int ok1=i,ok2=j;
				while(true)
				{
				   ok1=path[ok1][ok2];
				   if(ok1==-1)
					   break;
				   temp.insert(temp.begin(),ok1);
			   
				}
				
				temp.insert(temp.begin(),i);//把起点插入

				for(int z=0;z<temp.size();z++)
					cout<<temp[z]<<" ";
				cout<<endl;
			}
		}
	}

 

最终程序结果：

 

 附上源码地址：https://github.com/longpo/algorithm/tree/master/Floyd