floyd.cpp

#include "stdio.h" #include "math.h" #include "malloc.h" #include "string.h" #define m 6 #defin

/* * * * * * * * * * * * * * * * * * * * * * * * * * 
*              FLOYD ALGORITHEM                    *                  
*                VERSION 1.0                       *
*             Written By Shen Hui                  *
* * * * * * * * * * * * * * * * * * * * * * * * * */                                                 
/*输入N个字符型数据，并以ENTER结束*/
/*然后输入边表信息，下标从零开始*/
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define n 39
#define max 500
typedef struct
{
  char p[n];
  float w[n][n];
}graph;

graph *ga2;
int visit[n];
int path[n][n];
float C[n][n];
float A[n][n];

graph *creatd(graph *ga)
{
  int i,j,a,b;
  //float w;
  //printf("This Is Graph With Derection\n");
  ga=(graph*)malloc(sizeof(graph));
 // printf("now input point infomation:");
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      ga->w[i][j]=0;
  
 for(i=0;i<n;i++)
   scanf("%c",&ga->p[i]);
  printf("\n\n");
  ga->w[0][7]=20;
  ga->w[0][18]=20;
  ga->w[0][30]=3.1;
  ga->w[1][7]=70;
  ga->w[2][8]=44;
  ga->w[3][10]=44;
  ga->w[4][17]=32;
  ga->w[5][14]=20;
  ga->w[5][37]=11;
  ga->w[6][15]=20;
  
  ga->w[6][38]=2;
  ga->w[7][8]=50;
  ga->w[7][31]=1.2;
  ga->w[8][9]=37;
  ga->w[8][32]=4.2;
  ga->w[9][10]=20;
  ga->w[9][33]=7;
  ga->w[10][11]=20;
  ga->w[10][17]=20;
  ga->w[11][12]=20;
  
  ga->w[11][13]=23;
  ga->w[12][35]=1;
  ga->w[13][14]=20;
  ga->w[13][36]=6.2;
  ga->w[14][15]=20;
  ga->w[14][37]=3;
  ga->w[15][38]=2;
  ga->w[16][22]=20;
  ga->w[16][26]=0.2;
  ga->w[17][34]=1;
  
  ga->w[18][19]=20;
  ga->w[18][30]=1;
  ga->w[19][20]=23;
  ga->w[19][29]=0.5;
  ga->w[20][28]=1;
  ga->w[21][22]=65;
  ga->w[21][27]=60;
  ga->w[22][24]=29;
  ga->w[23][25]=0.3;
  ga->w[24][25]=10.4;
  
  ga->w[25][26]=30.1;
  ga->w[26][27]=75;
  ga->w[27][28]=60.6;
  ga->w[28][29]=19.4;
  ga->w[29][30]=20.5;
  ga->w[30][31]=20.1;
  ga->w[31][32]=68;
  ga->w[32][33]=48;
  ga->w[33][34]=30;
  ga->w[34][35]=22;
  
  ga->w[35][36]=21;
  ga->w[36][37]=42;
  ga->w[37][38]=50;

for(i=0;i<n;i++)
 for(j=0;j<n;j++)
	 if(ga->w[i][j]!=0)
		 ga->w[j][i]=ga->w[i][j];
  return(ga);
}

 

void transplant(float C[n][n],graph *ga2)
{
 int i,j;
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   {
    if((ga2->w[i][j]==0)&&(i==j)) C[i][j]=0;
      else if(ga2->w[i][j]==0) C[i][j]=max;
	   else  C[i][j]=ga2->w[i][j];}
}

void FLOYD(float C[n][n],float A[n][n])
{
 int i,j,k,next;
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   {
    if(C[i][j]!=max) path[i][j]=j+1;/*n*/
     else path[i][j]=0;
    A[i][j]=C[i][j];
   }
 for(k=0;k<n;k++)
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    if(A[i][j]>A[i][k]+A[k][j])    /*aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa*/
     {
      A[i][j]=A[i][k]+A[k][j];
      path[i][j]=path[i][k];
     }
 for(i=0;i<7;i++)
 {
  for(j=0;j<n;j++)
   {
    printf("%5.2f",A[i][j]);
    next=path[i][j];
    if(next==0)
     printf("   %d to %d no path    ",i+1,j+1);
    else
     {
      printf("  %d",i+1);
      while(next!=(j+1))                  /*n*/
       {
	printf("-->%d",next);             /*n*/
	next=path[next-1][j];             /*n*/
       }
      printf("-->%2d\n",j+1);
     }
   }
  printf("\n");
 }
}


void main()
{                   
  ga2=creatd(ga2);
  transplant(C,ga2);
  FLOYD(C,A);
}