aaa.c

对于无向图或有向图

//该程序实现如下功能：任意两个局之间的距离
//程序里用从1到73的数字表示各个支局，而100代表中心局D，101到105代表各个县局

#include   <stdio.h>   
#include   <stdlib.h>      
#include   <math.h>
//-----------图的邻接矩阵存储表示---------
#define INFINITY 99999
#define MAX_VERTEX_NUM 120
typedef struct {
int adj;  //VRType 是顶点关系的类型。对带权图，则为权值类型。
int info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
  
typedef struct  {
int vexnum;                      //图的当前顶点数
int arcnum;                      //图的当前弧数
int vexs[MAX_VERTEX_NUM];        //顶点向量
AdjMatrix arcs;                  //邻接矩阵     
}MGraph;


void CreateDN(MGraph *G);       //声明函数
void ShortestPath_FLOYD(MGraph *G);

void main()
{ 
  MGraph   G;   
  CreateDN(&G);   
  ShortestPath_FLOYD(&G);
 }

//下面是函数的具体实现
void CreateDN(MGraph *G)
{
//采用邻接矩阵表示法，构造有向网G
int i,j,k,m,n,dist;
printf("输入总顶点数和弧数: \n");
scanf("%d%d",&G->vexnum,&G->arcnum);  
//该图共有79个点，74是D点，75到79是各县局点。341条边
for(i=1;i<=G->vexnum;i++)
           G->vexs[i]=i;
 //初始化邻接矩阵
  for(i=1;i<=G->vexnum;i++)  
   for(j=1;j<=G->vexnum;j++){
	   if(i==j) G->arcs[i][j].adj=0;
	   else G->arcs[i][j].adj=INFINITY;
       G->arcs[i][j].info=1; }
  printf("\n");

  //输入各边的依附的顶点及其距离
  for(k=1;k<=G->arcnum;k++)
  {
  printf("输入该边的起点,终点,距离: \n");
  scanf("%d%d%d",&m,&n,&dist);  
  //scanf("%d%d%d",&m,&n,&dist);
  G->arcs[m][n].adj=dist;
  //if(!t) G->arcs[m][n].info=t;
   }//for
  
}//createDN

void ShortestPath_FLOYD(MGraph *G)
//用Floyd算法求有向网G的v0顶点到其余顶点v的最短路径及其带权长度
{
	int v,w,u,i;
    int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    float D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    for(v=1;v<=G->vexnum;v++)
	   for(w=1;w<=G->vexnum;w++)	{
		   D[v][w]=G->arcs[v][w].adj;
		   for(u=1;u<=G->vexnum;u++)  P[v][w][u]=0;		  
	if(D[v][w]<INFINITY) {
		P[v][w][v]=1; P[v][w][w]=1;} //if
	}//for

    for(u=1;u<=G->vexnum;u++)
	   for(v=1;v<=G->vexnum;v++)
		 for(w=1;w<=G->vexnum;w++)							
			    if(D[v][u]+D[u][w]<D[v][w]){
                D[v][w]=D[v][u]+D[u][w];
				for(i=1;i<=G->vexnum;i++)
					P[v][w][i] = P[v][u][i]||P[u][w][i];						
						            }  
    //打印最短路径  
    for(v=1;v<=G->vexnum;v++){
	printf("\n");
	for(w=1;w<=G->vexnum;w++)
		printf("%6.2f ",D[v][w]);
	}
	printf("\n\n");

    //打印最短路径经过的顶点
    for(v=1;v<=G->vexnum;v++)
	{
	  printf("\n");
	  for(w=1;w<=G->vexnum;w++)
	   if(w!=v){
		printf("\n");
		printf("过从%d到%d经的顶点序列为 ",v,w);
		for(i=1;i<=G->vexnum;i++)
		if(P[v][w][i]) printf("%d ", i);
		printf("\n");
	  }
	}
	}