多源最短路径之Floyd算法

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAX 999
using namespace std;
int n,m;
int e[MAX][MAX];
void Init()
{
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
        {
            if(i==j)
                e[i][j]=0;
            else
                e[i][j]=MAX;
        }
}
void Input()
{
    int a,b,c;
    for(int i=1; i<=m; ++i)
    {
        cin>>a>>b>>c;
        e[a][b]=c;
    }
}
void Floyd()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(e[i][j]>e[i][k]+e[k][j])
                    e[i][j]=e[i][k]+e[k][j];
}
void Output()
{
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            cout<<"dis["<<i<<"]["<<j<<"] = "<<e[i][j]<<endl;
}
int main()
{
    while(1)
    {
        cout<<"n"<<endl;//顶点个数
        cin>>n;
        if(!n) break;
        cout<<"m"<<endl;//边的个数
        cin>>m;

        Init();

        Input();

        Floyd();
        Output();
    }
}

Floyd算法是求多点最短路径的一种算法，其核心代码为

void Floyd()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(e[i][j]>e[i][k]+e[k][j])
                    e[i][j]=e[i][k]+e[k][j];
}