最短路之Floyd算法

问题

已知一张有向图，求出每个点到其他点的最短路径，也就是多源最短路径的问题。

解析

Floyd算法的本质是一种动态规划的思想，它的转移方程为：mp[i,j]=min(mp[i,k]+mp[k,j],mp[i,j])，其中mp[i,j]代表从i点到j点的最短距离，所以可以枚举i点和j点，更新每个i到j的最短距离再枚举k，但是这样枚举计算mp[i,j]，因为不能确定枚举的所有到k点为最短路径，一旦确定后，之后不会修改，所以应该先枚举k，再枚举i，j，这样就实现了Floyd算法。
从任意节点i到任意节点j的最短路径不外乎2种可能：
1)直接从节点i到节点j。
2)从节点i经过若干个节点k到节点j。
所以，我们假设mp(i,j)为节点i到节点j的最短路径的距离，对于每一个节点k，我们检查mp(i,k)+mp(k,j)<mp(i,j)是否成立，如果成立，证明从节点i到节点k再到节点j的路径比节点i直接到节点j的路径短，我们便设置mp(i,j)=mp(i,k)+mp(k,j)，这样一来，当我们遍历完所有节点k，mp(i,j)中记录的便是节点i到节点j的最短路径的距离。
初始的距离矩阵：
0 2 6 4
inf 0 3 inf
7 inf 0 1
5 inf 12 0
本题的最短路径矩阵：
0 2 5 4
9 0 3 4
6 8 0 1
5 7 10 0

设计

枚举顶点k ∈ [1,n]
           以顶点k为中介点，枚举所有顶点对i和j（i ∈ [1,n],j ∈1[1,n]）
                         如果dis[i][k] + dis[k][j] <dis[i][j]成立
                                       赋值dis[i][j] = dis[i][k] + dis[k][j]

分析

显而易见，Floyd算法有三层循环，所以该算法的复杂度为O(N³)，该算法可以计算最大10⁴的数据。

源码

https://github.com/Geedhayb/Geed/blob/master/Floyd.cpp