Floyed(floyd)算法详解

Floyd算法是一种全源最短路算法，也被称为插点法，它可以求解任意两点之间的最短路径。Floyd算法的时间复杂度为O(n^3)，适用于有向图或无向图，但前提是图中不存在负权回路。

Floyd算法的核心思想是动态规划，其核心思想是“三重循环”：枚举所有顶点对作为中间点，逐步缩小两个端点之间的距离。具体来说，我们可以使用一个二维数组dp[i][j]来存储从顶点i到顶点j的最短路径长度，若存在顶点k，使得从顶点i到顶点k经过顶点j且路径长度更短，则更新dp[i][j]的值为dp[i][k]+dp[k][j]。

下面我们来介绍Floyd算法的具体实现流程：

1. 初始化：建立一个二维数组（dp[n][n]）存储任意两点之间的最短路径长度。如果存在一条长度为d的边从i到j，则dp[i][j]=d；否则，dp[i][j]的值为正无穷大（我们可以用一个极大值代替正无穷大，比如1000000）。

2. Floyd算法的核心是三重循环，其中外层两重循环枚举任意两点，内层循环枚举中间点。具体实现过程为：

for (int k = 1; k <= n; ++k) {

for (int i = 1; i <= n; ++i) {

for (int j = 1; j <= n; ++j) {

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

}

}

}

3. 返回结果：当三重循环结束后，数组dp中存储的值即为任意两点之间的最短路径长度。

接下来我们来看一个具体的实例，以帮助理解Floyd算法的实现过程。下面是一个无向图，我们需要求出任意两点之间的最短路径长度。

根据上述流程，我们首先需要初始化dp数组，下面是初始状态：

```

dp[1][1]=0 dp[1][2]=2 dp[1][3]=6 dp[1][4]=4 dp[1][5]=5

dp[2][1]=2 dp[2][2]=0 dp[2][3]=3 dp[2][4]=1000000 dp[2][5]=11

dp[3][1]=6 dp[3][2]=3 dp[3][3]=0 dp[3][4]=7 dp[3][5]=1000000

dp[4][1]=4 dp[4][2]=1000000 dp[4][3]=7 dp[4][4]=0 dp[4][5]=1000000

dp[5][1]=5 dp[5][2]=11 dp[5][3]=1000000 dp[5][4]=1000000 dp[5][5]=0

```

接下来，我们开始进行三重循环，枚举任意两点之间的最短路径长度。下表给出的是第一次循环（k=1）之后的dp数组的状态。我们发现，当k=1时，从1到2、3到4、5到2、5到3的路径都变得更短了！

```

dp[1][1]=0 dp[1][2]=2 dp[1][3]=6 dp[1][4]=4 dp[1][5]=5

dp[2][1]=2 dp[2][2]=0 dp[2][3]=3 dp[2][4]=11 dp[2][5]=11

dp[3][1]=6 dp[3][2]=3 dp[3][3]=0 dp[3][4]=7 dp[3][5]=8

dp[4][1]=4 dp[4][2]=7 dp[4][3]=7 dp[4][4]=0 dp[4][5]=9

dp[5][1]=5 dp[5][2]=11 dp[5][3]=13 dp[5][4]=12 dp[5][5]=0

```

继续进行下一轮循环（k=2）之后的dp数组状态如下。当k=2时，从1到3、1到5、2到4的路径都更短了！

```

dp[1][1]=0 dp[1][2]=2 dp[1][3]=5 dp[1][4]=4 dp[1][5]=5

dp[2][1]=2 dp[2][2]=0 dp[2][3]=3 dp[2][4]=9 dp[2][5]=10

dp[3][1]=5 dp[3][2]=3 dp[3][3]=0 dp[3][4]=7 dp[3][5]=8

dp[4][1]=4 dp[4][2]=6 dp[4][3]=7 dp[4][4]=0 dp[4][5]=9

dp[5][1]=5 dp[5][2]=8 dp[5][3]=11 dp[5][4]=8 dp[5][5]=0

```

最后，进行最后一轮循环（k=3）之后，dp数组的状态如下。由于此时三重循环结束，因此dp数组中存储的值即为任意两点之间的最短路径长度。

```

dp[1][1]=0 dp[1][2]=2 dp[1][3]=5 dp[1][4]=4 dp[1][5]=5

dp[2][1]=2 dp[2][2]=0 dp[2][3]=3 dp[2][4]=9 dp[2][5]=10

dp[3][1]=5 dp[3][2]=3 dp[3][3]=0 dp[3][4]=7 dp[3][5]=8

dp[4][1]=4 dp[4][2]=6 dp[4][3]=7 dp[4][4]=0 dp[4][5]=9

dp[5][1]=5 dp[5][2]=8 dp[5][3]=11 dp[5][4]=8 dp[5][5]=0

```

在本例中，我们总共进行了三轮循环，但在实际应用中可能需要更多轮。Floyd算法的时间复杂度为O(n^3)，空间复杂度为O(n^2)。其实现简单，适用于求解稠密图的最短路径，但可能会比较慢。因此，在实际应用中，我们需要根据具体问题选择合适的算法。 如果你喜欢我们三七知识分享网站的文章， 欢迎您分享或收藏知识分享网站文章 欢迎您到我们的网站逛逛喔！https://www.37seo.cn/