floyd最短路算法 | Eternal_zttz

[Eternalzttz]

http://eternalzttz.com/floyd.html

Floyd算法是一种动态规划算法，适用于多源最短路径，相对于Dijkstra算法和SPFA算法，其算法复杂度较高，时间复杂度为O(n^3),但其理解较为容易，且代码简单。其基本思想便是对点松弛，在任意 i,j 顶点中，看是否存在顶底k,使得i -> k -> j 的距离小于i -> j的距离，如果存在，则对该两点进行松弛操作。