CC++ Floyd算法 (图的多源最短路径)

C/C++ Floyd算法 (图的多源最短路径) Floyd-Warshall算法，简称Floyd算法

该算法用于求解任意两点间的最短距离，时间复杂度为O(n^3)。 通常可以在任何图中使用，包括有向图、带负权边的图。

Floyd算法求得两点间的最短距离，需要借助邻接矩阵来存储边信息，通过每条路径的最佳子路径来得到两点的最短路径。

注：即使是单边路径，也并非其他路径的最佳子路径。

准备

我们采用下面这个有向图来解释该算法：

我们首先采用一个Map数组作为邻接矩阵，存入边信息：

#define INF 32767 //将不通的路径权值设置为INF
int Map[2000][2000]; //方便观赏直接定义大小 使用时可以采用动态扩容

//初始化传入点数即可
void initMap(int n) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (i == j) Map[i][j] = 0;
			else if (Map[i][j] == 0) Map[i][j] = INF;
		}
	Map[0][1] = 3;
	Map[0][2] = 8;
	Map[0][4] = -4;
	Map[1][3] = 1;
	Map[1][4] = 7;
	Map[2][1] = 4;
	Map[3][0] = 2;
	Map[3][2] = -5;
	Map[4][3] = 6;
}

当然，采用结构体更加推荐，这里为了方便就直接采用最简单的。

Floyd算法是采用两个表来存储路径信息，其中D表存储路径长度，S表存储路径前驱。

int D[n][n];
int S[n][n];

算法实现

我们可以看到，从点0到点3的最短路径很明显是0->4->3，可以看到其经过的路径中，0->4也是点0到点4的最短路径，也就是说，Floyd算法的思想就是找出点之间的最短路径，让其成为其他最短路径的子路径。就好比先找出0->4为最佳路径，在找点0到点3的最短路径时候，只需要比较0->1路径与0->4路径加上到点4路径的距离。

for (int i = 0; i < n; i++) 
	for (int j = 0; j < n; j++)
    	D[i][j] = Map[i][j]; //初始化D表，将邻接矩阵中的信息直接拷贝过来
for (int i = 0; i < n; i++) 
    for (int j = 0; j < n; j++) 
        S[i][j] = j; //初始化S表，将每条路的前驱点设置为终点

初始化后的D表、S表如下：


接下来我们就可以实现Floyd算法了：

for (int k = 0; k < n; k++)  //k作为中间点
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++)
   			if (D[i][j] > D[i][k] + D[k][j]) { //判断i->k->j的路径长度是否小于原本的路径长度
    			D[i][j] = D[i][k] + D[k][j];
    			S[i][j] = S[i][k]; //将i->j的前驱点设置为i->k的前驱点
   			}

经过循环后，可以得到最终的D表、S表如下：


到这，算法就结束了。

D表中的D[i][j]对应的值就是点 i 到点 j 的最短路径长度。而S表中的S[i][j]则表示的是其子最短路径的终点，如点0到点3的最短路径，对照S表，可以看到S[0][3]的值为4，那就说明点0到点3必定经过点4，再查看S[0][4]可以得到值为4也就是终点，即可得到点0到点3的最短路径为0->4->3。

倒着使用for循环即可输出路径。