ch6_5.c

清华出版社出版

#include <stdio.h>
#define M 10
#define MAX 100
void shortpath_DIJ(int ad[][M],int k,int pre[],
                   int dist[],int n)
{  int i,j,p,wm;
   k=k-1;
   for(i=0;i<n;i++)
   {  dist[i]=ad[k][i];
      if(dist[i]<MAX)  pre[i]=k+1;
      else             pre[i]=0;
   }
   pre[k]=0; dist[k]=0; ad[k][k]=1;
   for(j=0;j<(n-1);j++)
   {  wm=MAX;  p=-1;
      for(i=0;i<n;i++)
         if((ad[i][i]==0)&&(dist[i]<wm))
         {   p=i;
             wm=dist[i];
         }
      if(p==-1)  break;
      else{  ad[p][p]=1;
             for(i=0;i<n;i++)
                if(ad[i][i]==0)
                   if(dist[p]+ad[p][i]<dist[i])
                   {  dist[i]=dist[p]+ad[p][i];
                      pre[i]=p+1;
                   }
          }
   }
}

void main()
{   int n=7,i,j,k=1;
    static int ad[][M]={{0  ,13 ,8  ,MAX,30 ,MAX,32},
			{MAX,0  ,MAX,MAX,MAX,9  ,7 },
			{MAX,MAX,0  ,5  ,MAX,MAX,MAX},
			{MAX,MAX,MAX,0  ,6  ,MAX,MAX},
			{MAX,MAX,MAX,MAX,0  ,2  ,MAX},
			{MAX,MAX,MAX,MAX,MAX,0  ,17},
			{MAX,MAX,MAX,MAX,MAX,MAX,0}};
    static int pre[M],dist[M];
    shortpath_DIJ(ad,k,pre,dist,n);
    for(i=0;i<n;i++)
    {  for(j=0;j<n;j++)
	 printf("%-6d",ad[i][j]);
       printf("\n");
    }
    for(i=0;i<n;i++)
      printf("%d  ",dist[i]);
    printf("\n");
    for(i=0;i<n;i++)
      printf("%d  ",pre[i]);

}