Floyd 算法（Floyd-Warshall algorithm），又叫弗洛伊德算法、插点法，是一种在给定加权图里计算顶点间最短路径的算法，能正确处理有向图和带负权的最短路径问题。它的名字来自创始人之一、1978 年图灵奖得主、斯坦福大学计算机科学系教授罗伯特·弗洛伊德。

它和 Dijkstra 算法怎么分工呢？Dijkstra 算法算的是给定一个起点，到其他所有顶点的最短路径。而 Floyd 算法算的是所有顶点到所有顶点的最短路径，能回答任意两个顶点之间的最短路径。

它的基本思想其实很朴素，就是看 i->k + k->j 的距离，是不是比 i->j 直接走更近。i->j 表示两个顶点之间直接的距离，两个顶点之间有边就取这条边的权值，没有边，初始就设成无限远。i->k + k->j 表示 i、j 两个顶点绕经 k 顶点之后的距离。这个 k 顶点就像是插在 i 和 j 之间的一个中转站，所以它也叫插点法。

整个算法维护两个二维数组。数组 1 用来记录两点之间当前的最小权值，数组 2 用来记录 i、j 这条最短路径是绕经哪个 k 顶点变短的。

接下来，我们实现一遍 Floyd 算法，算一下 1 号顶点到 5 号顶点之间的最短路径。下面代码里最核心的是三层嵌套循环，它把图中任意两个顶点绕经 k 结点后会不会更近全都算了一遍。

#include <iostream>
#include <list>
using namespace std;

#define M 65535

// 定义顶点
const int vertex_size = 6;
int vertex[] = { 1, 2, 3, 4, 5, 6 };

// 定义边
int edges[][6] = {
	{ 0,  7,  9,  M,  M, 14},
	{ 7,  0,  10, 15, M, M},
	{ 9,  10, 0,  11, M, 2},
	{ M,  15, 11, 0,  6, M},
	{ M,  M,  M,  6,  0, 9},
	{14,  M,  2,  M,  9, 0}
};

void floyd()
{
	// 用于记录两个顶点之间的最小距离
	int others_others[vertex_size][vertex_size] = { 0 };
	for (int i = 0; i < vertex_size; ++i)
	{
		for (int j = 0; j < vertex_size; ++j)
		{
			others_others[i][j] = edges[i][j];
		}
	}

	// 用于记录两个顶点经过 x 顶点为最小距离
	int shortest_path[vertex_size][vertex_size] = { 0 };
	for (int i = 0; i < vertex_size; ++i)
	{
		for (int j = 0; j < vertex_size; ++j)
		{
			shortest_path[i][j] = -1;
		}
	}


	// 开始计算任意顶点经过 k 是否更近
	for (int k = 0; k < vertex_size; ++k)
	{
		for (int i = 0; i < vertex_size; ++i)
		{
			for (int j = 0; j < vertex_size; ++j)
			{

				// 经过 k 之后的距离
				int i_k_j = others_others[i][k] + others_others[k][j];
				int i_j = others_others[i][j];

				if (i_k_j < i_j)
				{
					// 记录 i 和 j 顶点经过 k 顶点距离更短
					shortest_path[i][j] = k;
					// 记录 i 和 j 之间更短的距离值
					others_others[i][j] = i_k_j;
				}
			}
		}
	}

	// 计算任意两个顶点之间的最短路径
	list<int> path;
	int start_vertex = 0;
	int end_vertex = 4;
	path.push_front(end_vertex);
	
	while (true)
	{
		end_vertex = shortest_path[start_vertex][end_vertex];
		if (end_vertex == -1)
		{
			path.push_front(start_vertex);
			break;
		}
		path.push_front(end_vertex);
	}

	for (auto v : path) cout << v + 1 << " ";
	cout << endl;
}

int main()
{
	floyd();
	return 0;
}

程序输出结果：

1 3 6 5

我们把 shortest_path 矩阵打印出来看：

for (int i = 0; i < vertex_size; ++i)
{	
	for (int j = 0; j < vertex_size; ++j)
	{
		cout.width(3);
		cout << shortest_path[i][j] << " ";
	}
	cout << endl;
}

 -1  -1  -1   2   5   2
 -1  -1  -1  -1   3   2
 -1  -1  -1  -1   5  -1
  2  -1  -1  -1  -1   2
  5   3   5  -1  -1  -1
  2   2  -1   2  -1  -1

每一行表示当前顶点到其他顶点的最短路径走法，看着是不是和 Dijkstra 有点像。矩阵里 -1 表示当前顶点到该顶点直接走就是最近的。如果填的是 2，就表示当前顶点到该顶点，绕经 2 号顶点会更近。

再把那个记录任意两顶点距离的 others_others 矩阵打印出来：

  0   7   9  20  20  11
  7   0  10  15  21  12
  9  10   0  11  11   2
 20  15  11   0   6  13
 20  21  11   6   0   9
 11  12   2  13   9   0

以后想直接查某两个顶点之间的最短距离，访问这个矩阵就行。