图论算法–Floyd算法

为了求出图中任意两点间的最短路径，当然可以把每个点作为起点，求解N次单源最短路径问题，不过，在任意两点间最短路问题中，图一般比较稠密，使用Floyd算法可以在O(n^3)的时间内完成，并且程序非常简单。

#include <iostream>
#include <cstring>

using namespace std;
const int N = 510;
int g[N][N];
int n,m;

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

int main(){
    cin >> n >> m;
    memset(g,0x3f,sizeof(g));
    for(int i=1;i<=n;i++) g[i][i] = 0;
    floyd();
    return 0;
}