floy.cpp

The method to find out the short line by Floyd algorithm

//Quy hoach dong
// Thuat toan Floy
// Tim duong di ngan nhat giua tat ca cac cap dinh
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define filein "Floy.inp"
#define fileout "Floy.out"
#define MAX 10000
#define NMAX 100
int n,u,v;
// Mang A la ma tran ke
int A[NMAX][NMAX];
// Mang D[i][j] de chua duong di ngan nhat tu i den j
int D[NMAX][NMAX];
// Mang S[i][j] de chua phan tu ngay sau cua i tren duong
// di tu i->j
int S[NMAX][NMAX];
void Input_Data()
{
    int i,j;
    FILE *fp;
    fp=fopen(filein,"r");
    fscanf(fp,"%d%d%d",&n,&u,&v);
    // Khoi tao ma tran ke
    for(i=1;i<=n;i++)         //Tao ma tran 0
    {
        for(j=1;j<=n;j++)
            A[i][j]=0;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            fscanf(fp,"%d",&A[i][j]);
            if(i!=j && A[i][j]==0)
            {
                A[i][j]=MAX;       //khong co duong di tu dinh i den dinh j
            }
        }
    }
    fclose(fp);
}
// Khoi tao ma tran ke
void Init()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            D[i][j]=A[i][j];
            if(D[i][j]==MAX)   // neu khong co duong di tu i->j
                S[i][j]=0;
            else               // neu co
                S[i][j]=j;     // nap dinh j vao mang S
        }
    }
}
// Tim duong di ngan nhat bang thuat toan Floy
void Floy()
{
    int i,j,k;
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(D[i][k]!=MAX && (D[i][j]>D[i][k]+D[k][j]))
                {
                    //Tim min D[i][j];
                    D[i][j]=D[i][k]+D[k][j];
                    S[i][j]=S[i][k];
                }
            }
        }
    }
}
// Xuat ket qua
void Output_Data()
{
    int i,j;
    FILE *fp;
    fp=fopen(fileout,"w");
    if(D[u][v]>=MAX)
        fprintf(fp,"+ Khong co duong di.\n");
    else
    {
        fprintf(fp,"+ Duong di ngan nhat:%d\n",D[u][v]);
        fprintf(fp,"Dinh %3d",u);
        while(u!=v)
        {
            fprintf(fp," -->%3d",S[u][v]);
            u=S[u][v];
        }
    }
}
int main()
{
    Input_Data();
    Init();
    Floy();
    Output_Data();
    return 0;
}