博客

floyd算法适用于求两个点之间的最短路径.

第一步：初始化矩阵

如果点i与点j之间是相连的它们之间的距离为x，那么a[i][j]=x;

如果点i与点j之间是不相连的，那么a[i][j]=∞：

如果点i等于点j，那么a[i][j]=0;

第二部：更新点i到点j的最短路径

假如点i与点k连通且点k与点j连通，如果点i到点k的距离加上点k到点j的距离小于之前点i直接到点j的距离则更新点i到点j的距离为点i到点k的距离加上点k到点j的距离，即a[i][j]=min(a[i][j],a[i][k]+a[k][j])。

核心代码：

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

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

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

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

时间复杂度O(n^3)

空间复杂度O(n^2)

但是该算法的时间复杂度较高所以不适合用于较多数据的计算。