1111.c

广西交通图,通过这个程序可以查找广西各个地方的最短距离

#include   <stdio.h>
#include    <stdlib.h>
#define    MAX    10000
#define   VEXTYPE   int      /*顶点值的类型*/ 
#define   ADJTYPE   int     /*权值类型*/ 
#define   MAXLEN    10      /*最大可能顶点数*/ 

/*邻接矩阵存储设计*/ 
typedef struct
 { VEXTYPE  vexs[MAXLEN];  /*顶点集*/ 
   ADJTYPE  arcs[MAXLEN][MAXLEN]; /*二维数组来存储有向网的邻接矩阵*/ 
   int     vexnum,arcnum;
   int     kind;
   } MGRAPH;

/*邻接矩阵建立算法*/ 
void  create_mgraph( MGRAPH  *pmg )
 { int i,j,k,h;
   char b,t;

   pmg->kind = 3;	/*有向网*/ 
   printf("请Please输入input顶点数vexnum，边数arcnum:");
   scanf("%d,%d",&i,&j);
   pmg->vexnum=i;  
 pmg->arcnum=j;

printf("Please input every value of vex:\n");
   for(i=0;i<pmg->vexnum;i++)
    { printf("第 %d个顶点值:",i+1);
      scanf("%d",&pmg->vexs[i] );
}
 printf("请输入各边或弧的信息（Please input every edge or arc's information）：");
for(i=0;i<pmg->vexnum;i++)
    { 
 for(j=0;j<pmg->vexnum;j++)
	          pmg->arcs[i][j]=MAX;   /*初始化邻接矩阵*/ 
       for( k=1; k<=pmg->arcnum ; k++ )
       {  
printf("\n请输入Please input 第 %dth edge or arc边或弧的（始点编号start，终点编号end）",k);
	         scanf("%d,%d",&i,&j);
	         while(i<1||i>pmg->vexnum||j<1||j>pmg->vexnum)
	         { 
printf("  编号有错Numer is error，input again请重新输入(1~%d):",pmg->vexnum);
	           scanf("%d,%d",&i,&j); 
}
	          printf("请输入该边的权值(Weight is):");
	          scanf("%d",&h);            pmg->arcs[i-1][j-1] = h; 
}
	     }	
 }
/*主函数*/ 
 void  main()
{   MGRAPH   graph, *mg = &graph ;
	   int    cost[MAXLEN][MAXLEN];  /*中间数组*/ 
	   int    path[MAXLEN];  /*路径序列数组*/ 
       int  s[MAXLEN];       /*已访问过的顶点集*/ 
	   int    dist[MAXLEN];   /*顶点间距离数组*/  
	   int     i,j,n,v0,min,u;
	  
 create_mgraph(mg);
	    printf(" 请输入源点 :"); 	    scanf("%d",&v0);
     v0--;
	    n=mg->vexnum;
	    for(i=0;i<n;i++)   /*初始化中间数组*/ 
	    { 
for(j=0;j<n;j++)
	         cost[i][j]=mg->arcs[i][j];
	       cost[i][i]=0;  
  }
	    for(i=0;i<n;i++)       /*初始化顶点间的距离数组*/ 
	    { 
dist[i]=cost[v0][i];
	        if( dist[i]<MAX && dist[i]>0 )
	           path[i]=v0; 
  }
	    for(i=0;i<n;i++)   /*初始化s数组*/ 
	      s[i]=0;
	    
s[v0]=1;    /*访问源点*/ 
	   
for(i=0;i<n;i++)  
	    { 
min = MAX ;    /*寻找距离最短的顶点来访问*/ 
	       u=v0;
	       for(j=0;j<n;j++)
	        { 
if( s[j] == 0 && dist[j]<min )
		        {  min=dist[j];
		            u=j;       /* u为目前所找到的距离最短的顶点*/ 
}
}
	      s[u]=1;     /*访问顶点u */ 
	      for(j=0;j<n;j++)  /*根据新访问的顶点u来调整顶点间的距离*/ 
	      { 
 if( s[j] == 0 && dist[u] + cost[u][j] < dist[j] )
		    { 
dist[j] = dist[u]+cost[u][j] ;
		        path[j]=u;         /*目前到达顶点j的最短路径的前一个顶点是u */ 
} }  }
         printf("%d to other vex shorted path is:",v0+1);
	     for(i=0;i<n;i++)  /*输出从源点到其余顶点的最短路径*/ 
	     {  
if( s[i]==1 )       /*顶点i被访问过，则从源点到i有最短路径*/ 
	         {  u = i ; /* u = 1*/ 	            while( u != v0 )   /*倒过来输出路径*/ 
		         {  printf("%d<-",u+1 ); 
		            u = path[u];
      }
		       printf("d=%d\n",dist[i]);
  }
		  else
		     printf(" %d<-%d无路可走not path. \n",i+1,v0+1 );
	      }     
 }