多源最短路：每一对顶点之间的最短路径

在一个图中用求单源最短路的方法对每一个顶点执行一次，即可得到每一对顶点的最短路径。由弗洛伊德提出的一个算法，和Dijkstra类似，它们得出的最短路径都是一步一步组合得到的。Floyd算法适合在稠密的矩阵图中使用，所以下面的例子我也用邻接矩阵表示法的方式来理解Floyd算法的运用。

看这样一个例子：

这是一个有向网图。表示这个图的邻接矩阵为：

首先看V0这个结点，从该图的邻接矩阵中，看0行0列以外的，且非对角线的元素。首先是D[ 1 ][ 2 ]=2。然后看D[ 1 ][ 2 ]元素在0行0列上的投影，D[ 0 ][ 2 ]+D[ 1 ][ 0 ]=11+6=17，因为17>2，所以不用跟新最短路径长度。然后矩阵里另一个元素D[ 2 ][ 1 ]=∞，在0行0列上的投影D[ 2 ][ 0 ]+D[ 0 ][ 1 ]=3+4=7，而7<∞，所以D[ 2 ][ 1 ]即顶点2到顶点1的最短路径长度被更新成7。这时对于V0这个顶点的访问就做完了。

接着到V1结点，看0行0列以外的，且非对角线的元素。D[ 2 ][ 0 ]=3，D[ 2 ][ 0 ]在第1行1列上的投影D[ 1 ][ 0 ]+D[ 2 ][ 1 ]=6+7=13，13>3，所以D[ 2 ][ 0 ]=3这个最短路径长度不变。然后看矩阵里另一个元素，D[ 0 ][ 2 ]=11，在第1行1列上的投影D[ 0 ][ 1 ]+D[ 1 ][ 2 ]=4+2=6，而6<11，所以D[ 0 ][ 2 ]这个最短路径长度要从11更新成6。此时对于结点V1的访问也就做完了。

最后到了V2这个结点，依然看0行0列以外的，且非对角线的元素。D[ 0 ][ 1 ]=4，D[ 0 ][ 1 ]在第2行2列上的投影D[ 0 ][ 2 ]+D[ 2 ][ 1 ]=6+7=13，13>4，所以D[ 0 ][ 1 ]=4这个最短路径长度不变。接着看矩阵里另一个元素D[ 1 ][ 0 ]=6，在第2行2列上的投影D[ 2 ][ 0 ]+D[ 1 ][ 2 ]=3+2=5，因为5<6，所以D[ 1 ][ 0 ]的最短路径长度要从6更新到5。

算法代码：

bool Floyd(Graph MyGraph, WeightType D[][MaxVertex], Vertex path[][MaxVertex]) 
{
	/*MyGraph是传进去的图,数组D是存两顶点的最短路径长度,path存最短路径*/
	Vertex i,j,k;
	
	/*初始化*/
	for (i=0; i<MyGraph->numv; i++) {
		for (j=0; j<MyGraph->numv; j++) {
			D[i][j]=MyGraph->wt[i][j];/*存图中的边权值*/
			path[i][j]=-1; 
		}
	}
	
	for (k=0; k<MyGraph->numv; k++) {
		for (i=0; i<MyGraph->numv; i++) {
			for (j=0; j<MyGraph->numv; j++) {
				if (D[i][k]+D[k][j]<D[i][j]) {
					D[i][j]=(D[i][k]+D[k][j];
					/*如果有负值圈*/
					if (i==j&&D[i][j]<0) {
						return false;/*返回错误标记*/
					}
					path[i][j]=k;
				}
			}
		}
	}
	return true; /*执行完毕，返回正确标记*/
}

时间复杂度为O（|V|³）。