ACM训练-floyd算法

问题描述：多源点问题和负权值图的最短路径

算法描述：Floyd算法是一个经典的动态规划算法。从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

源代码：

#include<stdio.h>
#define MAX 100000
int main()
{
    int n;
    int arcs[10][10],path[10][10];//pat[i][j]=k 表示从i到j会经过k  
    FILE *fp=fopen("floyd_data.txt","r");
    if(fp==NULL)
    {
        printf("open file error\n");
        return 0;
    } 
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            fscanf(fp,"%d",&arcs[i][j]);
            path[i][j]=j; //初始化 
        }
    }
    for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    if(arcs[i][k]+arcs[k][j]<arcs[i][j]) 
    {
        arcs[i][j]=arcs[i][k]+arcs[k][j];
        path[i][j]=k;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            printf("%d->%d:%d    ",i,j,arcs[i][j]);
            int t=i;
            while(t!=j)
            {
                printf("%d--",t);
                t=path[t][j];
            }  
            printf("%d",t);
            printf("\n");
        }
                
    }
    if(fclose(fp)!=0) printf(" close file error\n");
}

时间复杂度：O（n³）