floyd算法求最短路径数学公式

Floyd算法是一种动态规划算法，用于寻找加权图中多源最短路径。该算法的核心思想是：对于每一对顶点 u 和 v，以 k 为中间顶点，检查是否存在一条从 u 到 v 的更短路径。如果存在，就更新它们之间的距离。

在Floyd算法中，用d[i][j]表示从顶点i到顶点j的最短路径长度。假设图中有n个顶点，则算法的基本思路如下：

1. 初始化d[i][j]为图中i到j的边权，若i和j不相邻，则d[i][j]为无穷大。

2. 对于每一个顶点k，检查d[i][j]是否大于d[i][k]+d[k][j]，如果大于则更新d[i][j]为d[i][k]+d[k][j]。

3. 循环执行第2步，直到所有的顶点对之间的最短路径长度都求得。

因此，Floyd算法的数学公式为：

d[i][j] = min(d[i][j], d[i][k]+d[k][j])

其中，0 <= i,j,k < n。