最短路径 - 弗洛伊德算法（Floyd）和C/C++语言代码实现

1.算法介绍

弗洛伊德算法和Dijkstra算法被公认为最著名的两种最短路径求解算法。接下来介绍一下弗洛伊德的算法。 弗洛伊德算法的思想是：先初始化距离矩阵，然后从第一个点开始逐步更新矩阵的点值。 d[i][j]表示i点到j点的距离。第k次更新时，选择d[i][k]+d[k][j]和d[i][j]大小。如果前者较小，则更新该值，否则保持不变。

这个算法的核心点就是记录每一个点我们要努力到达每一个点

（看图，尝试用这张图来搭建）

2.算法实现：

通过权重矩阵找到图上每两点之间最近的距离矩阵。

从图的加权邻接矩阵A=[a(i,j)] n×n开始，递归进行n次更新，即从矩阵D(0)=A开始，根据公式，建立矩阵D (1) ;并使用相同的公式从 D (1) 构造 D (2);...;最后，使用相同的公式从 D(n-1) 构造矩阵 D(n)。矩阵D(n)的第i行j列的元素是从顶点i到顶点j的最短路径的长度。 D(n)称为图的距离矩阵。同时，还可以引入后继节点矩阵路径来记录两点之间的距离。最短路径。

使用松弛技术（松弛操作）对i和j之间的所有其他点进行松弛。所以时间复杂度为O(n^3)；

状态转移方程

状态转移方程如下：map[i,j]:=min{map[i,k]+map[k,j] ,map[i,j]};

map[i,j]显示i到j的最近距离，K是完整i,j的断点，map[n,n]的初始值必须为0或自定义特殊意义点

3。代码实现

参考代码，简化了输入操作和直接赋值。