floyd_warshall.c

Floyd_Warshall算法求最短路径

#include <stdio.h>
#include <string.h>

#define N 1000
#define MaxW 999999

int a[N][N];
int p[N];
int n,s,t;

int init()
{
    int i,j;
    scanf("%d",&n);
    scanf("%d%d",&s,&t);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            if (a[i][j]==0 && i!=j)
               a[i][j]=MaxW;
        }   
    return 0;
    
}

int out(int t)
{
    if (p[t]!=s) out(p[t]);
    printf("->%d",t);
    return 0;
}

int Floyd_Warshall()
{
    int i,j,k;
    memset(p,0,sizeof(p));
    for (k=1;k<=n;k++)
        for (i=1;i<n;i++)
            for (j=1;j<=n;j++)
            {
                if (p[j]==0 && a[i][j]<MaxW) p[j]=i;          
                if (a[i][j]>a[i][k]+a[k][j]&& i!=j)
                {
                     a[i][j]=a[i][k]+a[k][j];
                     p[j]=k;
                }
        }
    if (a[s][t]<MaxW) 
    {
       printf("The longth of the shortest path is %d\n",a[s][t]);
       printf("The shortest path is: ");
       printf("%d",s);
       out(t);
       printf("\n",s);
    }
    else printf("There is no path from %d to %d\n"); 
}


int main()
{
    init();

    Floyd_Warshall();
    
    system("PAUSE");	

    return 0;
}