Floyd算法优化

旧城等待， 2024-02-18 23:01 17阅读 0赞

经典实现

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]);
                }
            }
        }
        return ;
    }

利用矩阵的对称性

void Floyd_1(){
        for(int k = 1; k <= N; k++){
            for(int i = 1; i <= N; i++){
                int t = A[i][k];
                for(int j = 1; j <= i; j++){
                    A[i][j] = min(A[i][j], t+A[k][j]);
                    A[j][i] = A[i][j];
                }
            }
        }
        return ;
    }

只使用矩阵的下三角部分

void Floyd_2(){
        for(int k = 1; k <= N; k++){
            for(int i = 1; i <= N; i++){
                if(k != i){
                    int t = (k<i) ? A[i][k] : A[k][i];
                    for(int j = 1; j <= min(k,i); j++){
                        A[i][j] = min(A[i][j], t+A[k][j]);
                    }
                    for(int j = k+1; j <= i; j++){
                        A[i][j] = min(A[i][j], t+A[j][k]);
                    }
                }
            }
        }
        return ;
    }

跳过不存在的路径

void Floyd_3(){
        for(int k = 1; k <= N; k++){
            for(int i = 1; i <= N; i++){
                if(k != i){
                    int t = (k<i) ? A[i][k] : A[k][i];
                    if(t == Inf)  continue;
                    for(int j = 1; j <= min(k,i); j++){
                        A[i][j] = min(A[i][j], t+A[k][j]);
                    }
                    for(int j = k+1; j <= i; j++){
                        A[i][j] = min(A[i][j], t+A[j][k]);
                    }
                }
            }
        }
        return ;
    }

避免大量调用数学函数

void Floyd_4(){
        for(int k = 1; k <= N; k++){
            for(int i = 1; i <= N; i++){
                if(k != i){
                    int t = (k<i) ? A[i][k] : A[k][i];
                    if(t == Inf)  continue;
                    for(int j = 1; j <= ((k<i)?k:i); j++){
                        if(t+A[k][j] < A[i][j])  A[i][j] = t + A[k][j];
                    }
                    for(int j = k+1; j <= i; j++){
                        if(t+A[j][k] < A[i][j])  A[i][j] = t + A[j][k];
                    }
                }
            }
        }
        return ;
    }