Floyd最短路算法

简介

Floyd算法，通过中转点来更新两点之间的最短距离。与Dijkstra等算法不同，他们是求一个点到其他各点的最短路径，而Floyd算法可以求任意2点的最短距离。

算法步骤

1.将读入的边放到二维数组上，如果两点之间有边相连，那么两点之间的距离就是边的权值，否则设为无穷大。 2.枚举中转点k，对于任意两个点i,j（i<>j<>k），看看能不能通过k来更新i,j两点的最短距离，如果可以，那么当且仅当dis[i,j]>dis[i,k]+dis[k,j]。 3.做完之后，答案就是这个二维数组了。

代码

最核心的代码只有5行：

for k:=1 to n do for i:=1 to n do for j:=1 to n do if (dis[i,j]>dis[i,k]+dis[k,j]) then dis[i,j]:=dis[i,k]+dis[k,j];

复杂度及优缺点

时间复杂度: O(n3) ，空间复杂度: O(n2) 优点：代码量小，代码简单，可以算出任意两个点之间的最短距离。 缺点：耗时大，遇到大数据容易时间超限。

解题

在看题的时候，如果我们观察到数据范围N≤一个很小的数，且这题是要求最短路的，那么我们要想到Floyd算法。