当前位置：首页 >> 低调看直播体育app软件下载 >> C/C++jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播 >> 最短路径-Floyd

栏目分类

热门排行

最短路径-Floyd

来源：网络整理时间:2015-03-29 关键词:

本篇文章主要介绍了"最短路径-Floyd"，主要涉及到方面的内容，对于C/C++jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播感兴趣的同学可以参考一下：之前我们接触学习了Dijkstra算法求解一个顶点到其他各个顶点的最短路径和距离，但如果我们想知道每一对顶点的最短路径和距离时，可以通过以每一个顶点作为...

之前我们接触学习了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

即得到：

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;iA[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<><><>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

最终程序结果：