全源最短路问题

全源最短路问题

全源最短路问题–Floyd算法

Floyd算法，也就是弗洛伊德算法，用来解决全源最短路问题。就是对给定的图G，求任意两点u，v之间的最短路径长度，时间复杂度为O(n^3)。

由于n^3的复杂度决定了顶点数n的限制约在200以内，因此使用邻接矩阵来实现Floyd算法是非常合适且方便的。

Floyd算法基于一个事实：
如果存在顶点k，使得以k作为中介点时，顶点i和顶点j的当前最短距离缩短，则使用顶点k作为顶点i和顶点j的中介点，即
dis[i][k] +dis[k][j] < dis[i][j] 时，令

dis[i][j] = dis[i][k] +dis[k][j]
其中dis[i][j]表示从顶点i到顶点j的最短距离。

//基于上面的事实，Floyd算法的模板流程如下：枚举顶点 k 属于 [1,n]以顶点 k 作为中介点，枚举所有顶点对 i 和 j （i 属于 [1,n], j 属于 [1,n]）