C++ 最短路径算法 Floyd-Warshall 优化

#include<bits/stdc++.h> using namespace std;

int n; int f[5001][5001];

int main(){ scanf("%d", &n);

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        scanf("%d", &f[i][j]);
    }
}

for(int k=1;k<=n;k++){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
        }
    }
}

printf("%d\n",f[1][n]);

return 0;

}

优化建议

1. 循环顺序优化: Floyd-Warshall 算法的循环顺序可以影响效率。将 k 循环放在最外层可以提高效率，因为 k 循环只计算一次，而 i 和 j 循环需要计算 n 次。
2. 数据类型优化: 使用 int 类型存储数据可以减少内存占用，但如果数据范围过大，需要使用 long long 类型。
3. 空间复杂度优化: Floyd-Warshall 算法的时间复杂度为 O(n^3)，空间复杂度也为 O(n^3)。可以考虑使用稀疏矩阵存储数据，以降低空间复杂度。
4. 使用缓存: 可以使用缓存技术来存储中间计算结果，以减少重复计算，提高效率。
5. 并行计算: 可以使用多线程或多核处理器来并行计算，提高算法效率。

代码示例

#include<bits/stdc++.h>
using namespace std;

int n;
int f[5001][5001];

int main(){
    scanf("%d", &n);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d", &f[i][j]);
        }
    }

    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }
    
    printf("%d\n",f[1][n]);
    
    return 0;
}

总结

通过对代码进行优化，可以提高 Floyd-Warshall 算法的效率，降低运行时间和内存占用。在实际应用中，需要根据具体情况选择合适的优化策略。