最短路劲Floyd算法

Floyd算法是一种多源最短路径算法，用于计算图中任意两个顶点之间的最短路径。它通过动态规划的思想逐步更新路径的长度来计算最短路径。

Floyd算法的基本思想是通过一个中间顶点集合，逐个考察这个集合中的顶点，看是否可以通过这个中间顶点缩短路径长度。具体步骤如下：

1. 初始化一个二维数组D，其中D[i][j]表示顶点i到顶点j的最短路径长度。如果i和j之间有边相连，则D[i][j]为边的权值，否则为无穷大。
2. 对于每一个中间顶点k，考虑所有的一对顶点i和j，更新D[i][j]为D[i][k] + D[k][j]与D[i][j]的较小值。
3. 重复步骤2，不断更新D数组，直到所有顶点都被考虑为中间顶点。
4. 最后得到的D数组中，D[i][j]表示顶点i到顶点j的最短路径长度。

Floyd算法的时间复杂度为O(V^3)，其中V为图中顶点的个数。因此，Floyd算法适用于顶点数不太多的图。

需要注意的是，Floyd算法可以处理有向图和带负权边的图，但不能处理带有负权环的图，因为负权环会导致最短路径不存在。

总结起来，Floyd算法是一种多源最短路径算法，通过动态规划的思想逐步更新路径长度，可以计算出图中任意两个顶点之间的最短路径长度。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [图算法——求最短路径（Floyd算法）](https://blog.csdn.net/qq_61959780/article/details/129363941)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [最短路径（Dijkstra算法和Floyd算法）](https://blog.csdn.net/weixin_44267007/article/details/119770562)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]