图的最短路径2.txt

利用临界矩阵求解又向图的最短路径

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#define ING 9999
typedef int PatrMatrix;
typedef int DistancMatrix;
typedef struct ArcCell{
	int adj;/*顶点关系类型，用1表示相邻，0表示不相邻*/
}ArcCell,**AdjMatrix;/*邻接矩阵*/
typedef struct type{	
	char data[3];/*顶点值*/
}VertexType;
typedef struct{
	VertexType *vexs;/*顶点向量*/
	AdjMatrix arcs;/*邻接矩阵*/
	int vexnum,arcnum;/*图的顶点数和边数*/
}MGraph;
void InitGraph(MGraph *G)/*初始图*/
{ int i,nu,mu;
 printf("\n输入顶点的个数和（边）弧的个数：");
  scanf("%d%d",&nu,&mu);
  G->arcs=(ArcCell **)malloc(nu*sizeof(ArcCell *));
  for(i=0;i<nu;i++)/*分配邻接矩阵空间*/
      G->arcs[i]=(ArcCell *)malloc(nu*sizeof(ArcCell));
  G->vexs=(VertexType *)malloc(nu*sizeof(VertexType));/*分配顶点空间*/
  G->vexnum=nu;G->arcnum=mu;/*图的顶点数和边数*/
}
void InsertGraph(MGraph *G,int i,VertexType e)
{ if(i<0||i>G->vexnum) return;
  strcpy(G->vexs[i].data,e.data);
}
int Locate(MGraph G,VertexType v1)/*确定v1在图顶点中的位置*/
{ int i;
	for(i=0;i<G.vexnum;i++)
		 if(strcmp(v1.data,G.vexs[i].data)==0) return i;
  return -1;
}
void CreateUND(MGraph *G)/*采用数组（邻接矩阵）和邻接表表示无向图*/
{int i,j,k,*p,d,w;
 VertexType v1,v2;
 p=(int *)malloc(G->vexnum*sizeof(int)); 
 for(i=0;i<10;i++) p[i]=0;
 for(i=0;i<G->vexnum;++i)/*初始邻接表*/
 { for(j=0;j<G->vexnum;++j) G->arcs[i][j].adj=ING;}
 for(k=0;k<G->arcnum;++k)
 {printf("\n输入第 %d 条（边）弧相对的两个顶点值:\n",k+1);
  d=0;
  scanf("%s%s",v1.data,v2.data);/*输入相邻的两个点值*/
  printf("输入它们的权值: ");
  scanf("%d",&w);
  i=Locate(*G,v1);j=Locate(*G,v2);/*用i 和j来确定它们的位置*/
  G->arcs[i][j].adj=w;
 }
}
void Pint(MGraph G)/*输出邻接矩阵*/
{int i,j;
 for(i=0;i<G.vexnum;i++)
	{
	  for(j=0;j<G.vexnum;j++)
	  {if(G.arcs[i][j].adj!=ING)
			printf(" %d ",G.arcs[i][j].adj);
	  else {if(i==j)printf("0");
	        else printf(" ∞ ");}
	  }
      printf("\n");
 }
}
void ShortestPath(MGraph G,PatrMatrix p[20][20][20],DistancMatrix D[20][20])
      /*对顶点V和W之间的最短路径及其带权长度D[v][w].
	    若p[v][w][u]为1，则U是从V到W当前求得最短路径上的顶点*/
{ int v,u,i,w;
  for(v=0;v<G.vexnum;v++)/*对各点之间初始已知路径及距离*/
	  for(w=0;w<G.vexnum;++w)
	  {D[v][w]=G.arcs[v][w].adj;
	   for(u=0;u<G.vexnum;u++) p[v][w][u]=0;/*先初始没有过度点*/
	   if(D[v][w]<ING){p[v][w][v]=1;p[v][w][w]=1;}/*从V到W有直接路径*/
	  }
  for(u=0;u<G.vexnum;u++)/*看有否过渡点*/
	  for(v=0;v<G.vexnum;v++)
		  for(w=0;w<G.vexnum;w++)
			  if(D[v][u]+D[u][w]<D[v][w])/*从v经u到w的一条路径更短*/
			  {D[v][w]=D[v][u]+D[u][w];
			   for(i=0;i<G.vexnum;i++)/*表示有路径*/
				   p[v][w][i]=p[v][u][i]||p[u][w][i];
			  }
}
void main()
{ MGraph G;
 VertexType e;
 int i,j;
 PatrMatrix p[20][20][20];
 DistancMatrix D[20][20];
 InitGraph(&G);
 printf("顶点值： \n");
 for(i=0;i<G.vexnum;++i)/*给图顶点向量付值*/
 {scanf("%s",e.data);InsertGraph(&G,i,e);}
  CreateUND(&G);/*构造图结构*/
  printf("邻接矩阵为：\n");
  Pint(G);/*输出邻接矩阵*/
  ShortestPath(G,p,D);/*调用最短函数*/
  printf("最短路: \n");
  for(i=0;i<G.vexnum;i++)
  {  for(j=0;j<G.vexnum;j++)
	    if(i!=j) 
		 printf(" %s 到 %s 的最短路为 %d \n",G.vexs[i].data,G.vexs[j].data,D[i][j]);
     printf("\n\n");
  }	 
  getch();
}
/*可输入书中第191页*/