Floyed(floyd)算法详解

Floyd算法，也称为Floyd-Warshall算法，是一种用于解决所有最短路径问题的动态规划算法。它可以在有向图或有向加权图中找出所有顶点对之间的最短路径。

Floyd算法的基本思想是通过一个中间顶点集合，逐步更新每个顶点对之间的最短路径长度。算法的核心是一个二维数组D，其中D[i][j]表示从顶点i到顶点j的最短路径长度。算法的步骤如下：

1. 初始化二维数组D。对于有向图中的任意两个顶点i和j，如果存在边(i,j)，则D[i][j]为边(i,j)的权重；如果不存在边(i,j)，则D[i][j]为无穷大。

2. 对于中间顶点k，遍历所有顶点对(i,j)，更新D[i][j]的值。如果D[i][j]大于D[i][k] + D[k][j]，则更新D[i][j]为D[i][k] + D[k][j]。也就是说，如果通过顶点k可以找到一条路径比直接从顶点i到顶点j更短，就更新D[i][j]的值。

3. 重复步骤2，对所有中间顶点进行遍历，直到所有顶点对的最短路径长度都计算出来。

4. 最后得到的二维数组D中，D[i][j]表示从顶点i到顶点j的最短路径长度。

Floyd算法的时间复杂度为O(n^3)，其中n为顶点的数量。它可以解决图中所有顶点对之间的最短路径问题，包括有向图中的负权边，但是对于有负环的图则无法得到正确的结果。

下面我们通过一个实例来说明Floyd算法的使用。

假设我们有以下有向加权图：

```

4

(1)----->(4)

/|\ /|\

1| |5 1| |3

| | | |

\|/ \|/

(2)----->(3)

2

```

我们将每条边的权重表示在顶点对应的括号中。

使用Floyd算法，我们可以计算出任意两个顶点之间的最短路径长度。

首先，我们初始化二维数组D如下：

```

| 1 | 2 | 3 | 4 |

---|---|---|---|---|

1 | 0 | ∞ | ∞ | ∞ |

---|---|---|---|---|

2 | ∞ | 0 | ∞ | ∞ |

---|---|---|---|---|

3 | ∞ | ∞ | 0 | ∞ |

---|---|---|---|---|

4 | ∞ | ∞ | ∞ | 0 |

---|---|---|---|---|

```

其中∞表示无穷大。

然后，我们从顶点1开始遍历中间顶点，更新D的值：

```

| 1 | 2 | 3 | 4 |

--|---|---|---|---|

1 | 0 | 1 | 3 | ∞ |

--|---|---|---|---|

2 | 3 | 0 | 2 | ∞ |

--|---|---|---|---|

3 | ∞ | ∞ | 0 | ∞ |

--|---|---|---|---|

4 | 4 | ∞ | 6 | 0 |

--|---|---|---|---|

```

接下来，我们继续遍历顶点2作为中间顶点：

```

| 1 | 2 | 3 | 4 |

--|---|---|---|---|

1 | 0 | 1 | 3 | ∞ |

--|---|---|---|---|

2 | 3 | 0 | 2 | ∞ |

--|---|---|---|---|

3 | 5 | 6 | 0 | ∞ |

--|---|---|---|---|

4 | 4 | 5 | 7 | 0 |

--|---|---|---|---|

```

继续遍历，最终可以得到最后的结果：

```

| 1 | 2 | 3 | 4 |

--|---|---|---|---|

1 | 0 | 1 | 3 | 4 |

--|---|---|---|---|

2 | 3 | 0 | 2 | 5 |

--|---|---|---|---|

3 | 5 | 6 | 0 | 3 |

--|---|---|---|---|

4 | 4 | 5 | 7 | 0 |

--|---|---|---|---|

```

最终的结果表明：

- 顶点1到顶点4的最短路径长度为4，可以经过顶点2或顶点3；

- 顶点2到顶点3的最短路径长度为2；

- 顶点3到顶点1的最短路径长度为5。

通过这个例子，我们可以看到Floyd算法的求解过程。它逐步更新D的值，最终得到所有顶点对之间的最短路径长度。

总结来说，Floyd算法是一种解决所有最短路径问题的动态规划算法。它的时间复杂度为O(n^3)，可以用于解决有向图或有向加权图中的最短路径问题。通过逐步更新D的值，算法可以找到所有顶点对之间的最短路径长度。 如果你喜欢我们三七知识分享网站的文章， 欢迎您分享或收藏知识分享网站文章 欢迎您到我们的网站逛逛喔！https://www.37seo.cn/