图——Floyd算法

最短路径：
弗洛伊德算法
我们先看一下我们举例的图，如下图中右边的图，其中左边的Av[]数组存储的任意两个顶点之间的当前最短路径长度，pathv[]数组存储了任意两个顶点他们所在最短路径之间的中间点(v为下标)。

floyd1

执行思路：
对于每个顶点v，和任意一顶点对（i,j）,i不等于j,v不等于i,v不等于j，如果A[i][j]>A[i][v]+A[v][j],则将A[i][j]更新为A[i][v]+A[v][j]的值，并将path[i][j]改为v。

执行过程：
floyd2

首先我们一共所有的情况为{0,1}，{0,2}……
初始化后，第一次，即当v=0时，发现所有情况中的{0,1}，此时i=0,j=1,v=0,v=i了，不满足条件，所以这个点跳过。很好理解，因为此时：式子”A[0][1]>A[0][0]+A[0][1]”明显不成立，所以这种类型跳过，同样的{0,2}，{0,3}，{0,4}，这几个点也跳过，这也是为什么上面有说i不等于j,v不等于i,v不等于j的原因。接着我们来到{1,2},此时对应的式子为“A[1][2]>A[1][0]+A[0][2]”,我们需要去判断大小，A[1][3]在A数组中为4，A[1][0]值为无穷，A[0][2]值也为无穷，所以式子不成立，不需要更新path数组。
接着再看下一个情况{1，3},i=V，所以跳过，再下一个{2,0},j=v所以也跳过。再下一个{2,1}，现在对应的式子为A[2][3]>A[2][0]+A[0][3],对应的值分别为2,3,7，式子不成立，也不需要更新。再下一对{3,0}，j=v跳过。再下一对{3,1},A[3][1]值为无穷，式子一定不成立，所以也不需要更新。最后看{3，2}，A[3][0]也为无穷大，所以，对于v=0这一情况，path数组不需要更新。

第二次，当v1时，也这样一个一个去比较，我就不细说了，其中，当为{0,2}时，式子为A[0][2]>A[0][1]+A[1][2],其中的值分别为无穷大，5,4。明显，式子成立，所以，此时将A[0][2]更新为9，将path[0][2]更新为1，表示其中间结点为1。然后再一次一个一个的对比，不再赘述。

floyd3

第三次，v=2,第四次，v=3，就这样循环比较，重复做上面的事情，更新A[]数组和path[]数组。

接着我们再看一下如何通过更新过的path[]数组去查找任意两个点的最短路径。例如：如果我们要寻找从1到0的最短路径是什么：首先查path[1][0]=3,说明1和0之间的中间点为3，所以将3标出，然后查path[1][3]=-1，说明从1到3有直接的边（这里path数组的值为-1，都说明两个点之间有直接相连的点，算是一个标记）。然后查path[3][0]=2，说明3和0之间又有中间点2，所以将2标出，然后查path[3][2]=-1,说明3和2之间也有直接的线相连，然后再查path[2][0]=-1,说明也有直接相连的边。此时从1到0的最短路径已经找出来了，就是分别这些个-1的边，为1->3->2->0。

floyd4

然后这个通过path数组查找是实现任意两个点之间的额最短路径的算法为（递归）：
u,v分别是从顶点u到顶点v

然后我们再看一下弗洛伊德算法的实现代码：
n为图中顶点的个数，MGraph[][]是图的邻接矩阵存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Floyd(int n,float MGraph[][n],int Path[][n])
{
	int i,j,v;
	int A[n][n];
	for(i=0;i<n;++i)//初始化
		for(j=0;j<n;++j)
		{
			A[i][j]=MGraph[i][j];
			Path[i][j]=-1;
		}
	for(v=0;v<n;++v)
		for(i=0;i<n;++i)
			for(j=0;j<n;++j)
				if(A[i][j]>A[i][v]+A[v][j])
				{
					A[i][j]=A[i][v]+A[v][j];
					Path[i][j]=v;
				}
}