Floyed(floyd)算法详解

Floyd算法，也称为插头DP算法，是一种重要的动态规划算法。该算法被广泛应用于图论中寻找最短路径的问题。

算法思想及原理：

Floyd算法是通过动态规划来实现的。假设给定一个无向图G=(V,E)，其中V是顶点的集合，E是边的集合。对于图中每对顶点i, j(i,j∈V)，定义dis(i,j)为i到j的最短路径距离，假设k是1~n中的任意一点，若i~k的最短路径距离为dis(i,k),k~j的最短路径距离为dis(k,j),则i~j的最短路径距离为dis(i,k)+dis(k,j)。因此，Floyd算法依次计算顶点之间的最短路径，并以此更新dis矩阵。

具体步骤：

1. 初始化dis矩阵，初值为两点之间边的权值。

2. 对于每一个顶点k，如果dis(i,j)>dis(i,k)+dis(k,j)，则更新dis(i,j)为dis(i,k)+dis(k,j)。

3. 扫描整个dis矩阵，得到每对点之间的最短路径长度。

算法优缺点：

优点：Floyd算法可以求解任意两点之间的最短路径。同时，该算法结构简单，易于实现，是一种比较通用的算法。

缺点：Floyd算法的时间复杂度较高，为 $O(n^3)$。

算法案例：

例如，有一张无向图如下所示：

```

1--2

| /|

|/ |

3--4

```

假设该无向图的邻接矩阵如下所示：

```python

graph = [

[0, 2, 6, 4],

[inf, 0, 3, inf],

[7, inf, 0, 1],

[5, inf, 12, 0]

]

```

其中，inf表示两点之间没有边相连。我们需要求解任意两点之间的最短路径。

按照Floyd算法的流程，首先进行初始化操作。由于对于任意一对不相邻的顶点，其距离均为inf，因此dis矩阵的初值为：

```

[[0, 2, 6, 4],

[inf, 0, 3, inf],

[7, inf, 0, 1],

[5, inf, 12, 0]]

```

然后，我们开始第一次循环，扫描整个矩阵，寻找每对顶点之间经过中间点k的最短路径。k的取值范围是1~n。对于每一对顶点i,j，我们用dis(i,k)+dis(k,j)来更新dis(i,j)的值。

第一次循环结束后，dis矩阵的值变为：

```

[[0, 2, 5, 4],

[inf, 0, 3, inf],

[7, 9, 0, 1],

[5, 7, 10, 0]]

```

此时，对于顶点4来说，与顶点1、顶点2、顶点3之间的最短路径均已经求解出来。因此，我们开始第二次循环，此时k的取值范围是2~n。

第二次循环结束后，dis矩阵的值变为：

```

[[0, 2, 5, 4],

[inf, 0, 3, inf],

[7, 9, 0, 1],

[5, 7, 10, 0]]

```

此时，对于所有的顶点来说，与其它顶点之间的最短路径均已经求解出来。因此，Floyd算法的计算过程结束。

最终得到的dis矩阵如下所示：

```

[[0, 2, 5, 4],

[9, 0, 3, 12],

[7, 9, 0, 1],

[5, 7, 10, 0]]

```

其中，第i行第j列的元素表示点i到点j的最短路径长度。

总结：

Floyd算法是一种比较通用且实用的最短路径算法。虽然该算法的时间复杂度较高，但是对于顶点数比较少的图而言，其运算时间不会太长。在实际应用中，如果需要求解的最短路径不是特别复杂，Floyd算法是一个不错的选择。 如果你喜欢我们三七知识分享网站的文章， 欢迎您分享或收藏知识分享网站文章 欢迎您到我们的网站逛逛喔！https://www.37seo.cn/