本文共 2478 字，大约阅读时间需要 8 分钟。

Floyd算法是一个经典的动态规划算法。简单地说，首先我们的目标是寻找从顶点 i 到顶点 j 的最短路径。

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

核心思想：本质就是逐步尝试在原路径中每次加入一个顶点k作为中间结点，所以代码的最外层循环就是for (int k = 0; k < G.numVEXS; k++)//中间点k

算法过程：

1）首先把初始化距离数组D为图的邻接矩阵arc，路径数组P初始化为P[i][j]=j（初始化时由于 i 是直接到 j 的，所以 i 的后继结点就是 j ）; 2）对于每一对顶点 i 和 j，遍历所有顶点，看看是否存在一个顶点 k 使得从 i 到 k 再加上 k 到 j 比直接从 i 到 j 的路径更短。如果是就更新D[i][j]。 递推关系式为： 如果 D[i][k]+D[k][j] < D[i][j] 则D[i][j] = D[i][k]+D[k][j] 注意！！！：仔细思考递推关系式会发现由于D[i][i]始终为0，所以 i 、j 、k 在for循环中是顺序还是逆序都没关系。 举个例子，比如我在求D^k [5][8]假设此时中间顶点为4，那么D^k [5][8]=min{D^k-1 [5][8],D^k-1 [5][4]+D^k-1 [4][8]},那么我接下来求其它的D^k [i][j]时肯定不会用到D^k [5][8];（因为这一轮k的值固定为4了） 又比如我在求D^k [4][8]假设此时中间顶点为4，由于D[4][4]为0,所以D^k [4][8]仍然等于D^k-1 [4][8]; 综上，所以D^k和D^k-1可以在同一个数组内完成更新，不用担心子问题的解被覆盖的风险。

#include
   
    using namespace std;#define MAXVEX 9#define INFINITY 65536typedef struct {   	int D[MAXVEX][MAXVEX];	int P[MAXVEX][MAXVEX];	int numVEXS;//顶点个数}MGraph;void ShortestPath_Floyd(MGraph&G);void PrintPath(MGraph&G, int v, int w);int main() {   	MGraph G;	G.numVEXS = 9;	for (int i = 0; i < G.numVEXS; i++)		for (int j = 0; j < G.numVEXS; j++)		{   			if (i < j)				G.D[i][j] = INFINITY;			if (i == j)				G.D[i][i] = 0;		}	G.D[0][1] = 1; G.D[0][2] = 5;	G.D[1][2] = 3; G.D[1][3] = 7; G.D[1][4] = 5;	G.D[2][4] = 1; G.D[2][5] = 7;	G.D[3][4] = 2; G.D[3][6] = 3;	G.D[4][5] = 3; G.D[4][6] = 6; G.D[4][7] = 9;	G.D[5][7] = 5;	G.D[6][7] = 2; G.D[6][8] = 7;	G.D[7][8] = 4;	for (int i = 0; i < G.numVEXS; i++)		for (int j = 0; j < G.numVEXS; j++)		{   			if (i < j)				G.D[j][i] = G.D[i][j];		}	for (int i = 0; i < G.numVEXS; i++)		for (int j = 0; j < G.numVEXS; j++)			G.P[i][j] = j;	//以上为D和P的初始化	ShortestPath_Floyd(G);	PrintPath(G, 0, 8);	system("pause");	return 0;}void ShortestPath_Floyd(MGraph&G) {   	for (int k = 0; k < G.numVEXS; k++)//中间点k		for (int v = 0; v < G.numVEXS; v++)//起点v			for (int w = 0; w < G.numVEXS; w++) {   //终点w				if (G.D[v][w] > G.D[v][k] + G.D[k][w])				{   					G.D[v][w] = G.D[v][k] + G.D[k][w];//动态规划					G.P[v][w] = G.P[v][k];//说明v到w的最短路径必经过k点，所以v到w的最短路径中v的后继结点也就是v到k的最短路径中v的后继结点					//P[v][w]表示v到w的最短路径中v的后继结点				}			}}void PrintPath(MGraph&G, int v, int w) {   	int temp = G.P[v][w];	cout << v << "-->";	while (temp != w)	{   		cout << temp << "-->";		temp = G.P[temp][w];	}	cout << w << endl;}
   

时间复杂度O（n³）