Floyd 알고리즘 학습 (최 단 경로)

#include 
#include 

#define MAXSIZE 100
#define MAXCOST 99
typedef struct

{
    int vertex[MAXSIZE];
    int edges[MAXSIZE][MAXSIZE];

} MyGraph;

void GrarhPrint(MyGraph*g,int n);
void CreateMGraph(MyGraph*g,int e,int n);
void Floyd(MyGraph*g,int n);
void Ppath(int path[][MAXSIZE],int i,int j);
void Dispath(int A[][MAXSIZE],int path[][MAXSIZE],int n);

int main()
{
    MyGraph *g=(MyGraph*)malloc(sizeof(MyGraph));
    CreateMGraph(g,10,6);
    Floyd(g,6);
    return 0;
}
void CreateMGraph(MyGraph*g,
                  int e,//  
                  int n //   
                 )

{
    int i,j,k,m;
    printf("Input data of vertex(0~n-1):
");

    for(i=0; ivertex[i]=i; //   0~n-1      
    }
    //      ，         
    for(i=0; ifor(j=0; jif(i==j)
                g->edges[i][j]=0;
            else
                g->edges[i][j]=MAXCOST;//99   
        }
    }
    //    ，       
    for(k=0; kprintf("Input edge of(i,j) and edge of size:");
        scanf("%d%d%d",&i,&j,&m);
        g->edges[i][j]=m;
    }
    GrarhPrint(g,n);
}
//   
void GrarhPrint(MyGraph*g,int n)
{
    int i=0;
    int j=0;
    for(i=0; ifor(j=0; jif(g->edges[i][j]==MAXCOST||i==j)
                printf("∞\t");
            else
                printf("%d\t",g->edges[i][j]);//               
        printf("
");
    }
}
void Floyd(MyGraph*g,int n)
{
    int A[MAXSIZE][MAXSIZE],path[MAXSIZE][MAXSIZE];
    int i,j,k;
    for(j=0;j//   
    {
        for(i=0;iedges[i][j];
            path[i][j]=-1;
        }
    }
    for(k=0;kfor(i=0;ifor(j=0;jif(A[i][j]>A[i][k]+A[k][j])
                {
                    A[i][j]=A[i][k]+A[k][j];
                    path[i][j]=k;
                }
            }
        }
    }
    Dispath(A,path,n);
}
void Ppath(int path[][MAXSIZE],int i,int j)
{
    int k;
    k=path[i][j];
    if(k!=-1)//  Vk    
    {
        Ppath(path,i,k);//   Vi      Vk
        printf("%d,",k);//    Vk   k
        Ppath(path,k,j);//   Vk       Vj
    }
}
void Dispath(int A[][MAXSIZE],int path[][MAXSIZE],int n)
{               //      
    int i,j;
    for(i=0;ifor(j=0;jif(A[i][j]==MAXCOST)//MAXCOST      
            {
                if(i!=j)
                    printf(" %d %d    !
",i,j);
            }
            else
            {
                printf(" %d %d     :%d,  ：",i,j,A[i][j]);
                printf("%d,",i);//          i
                Ppath(path,i,j);//            
                printf("%d
",j);//          
            }
        }
    }
}