C++实现多源最短路径之Floyd算法示例

#include<cstdio>#include<cstring>#include<iostream>#define MAX 999using 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();  }}

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