最短路径Floyd算法

#include<iostream>
using namespace std;
int a[10][10];  //存储点与点之间的距离
int n;          //顶点数
int e;          //边数
const int inf=999999999;    //无穷大
int x,y,z;      //x到y的距离为z
int i,j,k;      //循环变量

void Create()
{
    cin>>n>>e;
    //初始化邻接矩阵
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
        {
            if(i==j)
                a[i][j]=0;
            else
                a[i][j]=inf;
        }

    for(i=1; i<=e; i++)
    {
        cin>>x>>y>>z;   //将x,y之间的距离置为z
        a[x][y]=z;
    }
}

void Floyd()
{
    for(k=1; k<=n; k++)         //进行n次迭代
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
            {
                if(a[i][k]<inf && a[k][j]<inf && a[i][j]>a[i][k]+a[k][j])//k为通过哪个点
                    //a[i][k]<inf&&a[k][j]<inf是防止a[i][k]+a[k][j]超出了int的最大范围
                    a[i][j]=a[i][k]+a[k][j];//通过其他点可以找到更短的路径
            }

    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(i!=j)
                cout<<i<<"号城市到"<<j<<"号城市最短路径为:"<<a[i][j]<<endl;
}

int main()
{
    Create();
    Floyd();
    return 0;
}

测试数据：
4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12