弗洛伊德算法（Floyd）

Floyd 算法（Floyd-Warshall algorithm）又称为弗洛伊德算法、插点法，用于在给定的加权图中计算两个顶点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

Floyd 算法和 Dijkstra 算法对比话，Dijkstra 算法可以计算给定起始点到其他所有顶点的最短路径。Floyd 算法能够计算所有顶点到所有顶点的最短路径，可以用于查询任意两个顶点之间的最短路径。

Floyd 算法基本思想，是计算出 i->k + k->j 的距离是否比 i->j 的距离更近。i->j 表示两个顶点之间直接的距离，如果两个顶点有边则具有有限的距离，如果两个顶点没有边，初始时设置为无限远。i->k + k->j 表示 i、j 两个顶点经过 k 顶点后的距离。这个 k 顶点就像是插入到 i 和 j 之间的顶点，所以也叫做插点法。

算法维 2 个二维数组，数组 1 用于记录两点之间的最小权值，数组 2 用于记录 i j 经过 k 顶点距离变得更短。

接下来，我们实现 Floyd 算法计算 1 顶点和 5 顶点之间的最短路径，下面代码中最核心的代码是 46-67 行代码，三层嵌套循环计算了图中任意两个顶点经过 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 顶点会更更近。

打印下用于记录任意两顶点距离的 ohters_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

如果想直接获得某两顶点之间距离，直接访问该矩阵即可。