Floyd算法

基本概念

多源最短路，即要求算出图中每两个顶点之间的最短路。一种方法是把n个点分别当成源点用Dijkstra算，时间复杂度是O(n3)，优化后也可以变为O(n2logn)。另一种方法就是经典Floyd算法，虽然复杂度是O(n3)，但是代码只有4行。Floyd算法本质上是一个动态规划算法。

经典实现

void Floyd(){
    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]);
            }
        }
    }
}