shortpath.cpp

数据结构清华大学出版社严蔚敏,吴为民编著的课后习题实验源代码

#include <stdio.h>
#include <conio.h>
#include <string.h>
#define CityNum      40        //最大城市结点数
#define NameLenght   12        //城市名字长度
#define Infinity     10000     //若城市间没有路径距离设定为Infinity
typedef char Vextype[NameLenght];
typedef int Arctype;
typedef struct
     { Vextype vexs[CityNum];              // 顶点数组
       Arctype  arcs[CityNum][CityNum];    //边矩阵，权值wij
       int  vexnum,arcnum;                 //顶点数,边数
      } Mgraph;

char *CityNameFile="cityname.txt";         //城市名数据文件
char *CityPathFile="citypath.txt";         //城市边数据文件
char *MinPathDataFile="shortpath.txt";     //最短路径数据文件
/*-----------确定城市名城的位置------------*/
int search(Mgraph G,char *p)
  { int i=0;
    while(i<G.vexnum)
     { if(!strcmp(G.vexs[i],p)) return(i);
       i++;
       }
    return(-1);
    }

 /*-----------输入城市名称数据------------*/
int InputCityNode(Mgraph *G)
  { int i,n;
    FILE *fp;
    if(!(fp=fopen(CityNameFile,"r")))
     { printf("城市数据文件不存在\n");
       getch();
       return(0);
     }
    fscanf(fp,"%d",&(G->vexnum));
  if(!G->vexnum)
    { printf("文件中无城市数据!\n");
      getch();
      return(0);
      }
   for(i=0;i<G->vexnum;i++) fscanf(fp,"%s",G->vexs[i]);
   fclose(fp);
   return(1);
   }
  /*-----------输读入城市边数据------------*/
int InputCityArc(Mgraph *G)
  { int i,j,k,val;;
    FILE *fp;
    char city1[NameLenght],city2[NameLenght];
    for(i=0;i<CityNum;i++)
     for(j=0;j<CityNum;j++)
	G->arcs[i][j]=Infinity;
   if(!(fp=fopen(CityPathFile,"r")))
   { printf("城市路径数据文件不存在!\n");
     getch();
     return(0);
     }
  fscanf(fp,"%d",&(G->arcnum));
  if(!(G->arcnum))
    { printf("文件中无城市路径数据!\n");
      getch();
      return(0);
      }
   for(i=0;i<G->arcnum;i++)
    { fscanf(fp,"%s%s%d",city1,city2,&val);
      j=search(*G,city1);
      k=search(*G,city2);
      if(j==-1||k==-1)
	{ printf("%d 城市名--%s--%s错误!\n",i,city1,city2);
	  getch();
	  fclose(fp);
	  return(0);
	  }
      G->arcs[j][k]=G->arcs[k][j]=val;
     }
    fclose(fp);
   return(1);
   }
int InputMinPath(int dist[][CityNum],int Path[][CityNum],int *NodeNum)
 {int i,n;
  FILE *fp;
  if(!(fp=fopen(MinPathDataFile,"rb")))
    { printf("最小路径数据文件不存在!\n");
      getch();
      return(0);
      }
   fread(&n,sizeof(int),1,fp);
   for(i=0;i<n;i++)
     fread(dist[i],sizeof(int),n,fp);
   for(i=0;i<n;i++)
     fread(Path[n],sizeof(int),n,fp);
   fclose(fp);
   *NodeNum=n;
   return(1);
   }

void shorttestpath()
{
  int i,j,k,NodeNum,EgeNum,val;
  Mgraph G;
  //int arc[CityNum][CityNum];      //权值矩阵
  //char city[CityNum][NameLenght];         //城市结点
  int dist[CityNum][CityNum];     //最短路径长度矩阵
  int Path[CityNum][CityNum];     //最短路径矩阵
  char city1[NameLenght],city2[NameLenght];
  FILE *fp;
 /*-----------读入城市结点数据------------*/
   if(!InputCityNode(&G)) return;
   for(i=0;i<G.vexnum;i++)
    { printf("%s\n",G.vexs[i]);
      }
   getch();
  /*------------读入城市间边的数据----------*/
  if(!InputCityArc(&G)) return;

  /*------------计算最短路径--------------*/
  for(i=0;i<G.vexnum;i++)
     { for(j=0;j<G.vexnum;j++)
	 { dist[i][j]=G.arcs[i][j];
	   if(G.arcs[i][j]<Infinity)
	     Path[i][j]=i;
	   else
	     Path[i][j]=-1;
	   }
       dist[i][i]=0;
       }
  for(k=0;k<G.vexnum;k++)
      for(i=0;i<G.vexnum;i++)
	  for(j=0;j<G.vexnum;j++)
	      if(dist[i][k]+dist[k][j]<dist[i][j])    //插入结点k
		 {
		   dist[i][j]=dist[i][k]+dist[k][j];
		   Path[i][j]=Path[k][j];
		 }
  for(i=0;i<G.vexnum;i++)
   { for(j=0;j<G.vexnum;j++)
	if(j%10) printf("%6d",dist[i][j]);
	else printf("%6d\n",dist[i][j]);;
      printf("\n");
      getch();
      }
  getch();
  for(i=0;i<G.vexnum;i++)
    { for(j=0;j<G.vexnum;j++)
	printf("%3d",Path[i][j]);
      printf("\n");
      }
  getch();
  /*-----------保存最小路径数据------------*/
   if(!(fp=fopen(MinPathDataFile,"wb")))
    { printf("保存数据的文件未打开!\n");
      getch();
      return;
      }
   fwrite(&G.vexnum,sizeof(int),1,fp);
   for(i=0;i<G.vexnum;i++)
     fwrite(dist[i],sizeof(int),G.vexnum,fp);
   for(i=0;i<G.vexnum;i++)
     fwrite(Path[i],sizeof(int),G.vexnum,fp);
   fclose(fp);
   }
/*----------------------------------------------------*/
/*      求一个城市到其它城市的最短路径                */
/*----------------------------------------------------*/
void One_To_Other_Path()
 { int i,j,k,NodeNum,StartNode;
   Mgraph G;
  // char city[CityNum][NameLenght];    //城市结点
   int dist[CityNum][CityNum];        //最短路径长度矩阵
   int Path[CityNum][CityNum];        //最短路径矩阵
   int top,PathStack[CityNum];
   char city1[NameLenght];
   FILE *fp;
/*-----------读入城市结点数据------------*/
   if(!InputCityNode(&G)) return;
/*-----------输入最小路径数据------------*/
   if(!InputMinPath(dist,Path,&NodeNum)) return;
/*-----求一个城市到其它城市的最短路径-----*/
   printf("输入起点城市名字:");
   do{
      scanf("%s",city1);
      StartNode=search(G,city1);
      if(StartNode==-1)
	printf("城市名字错误，请重新输入:");
      else
	break;
      }while(1);
   for(i=0;i<NodeNum;i++)
     { top=0;
       if(StartNode==i) continue;
       if(dist[StartNode][i]==Infinity)
	{ printf("%s不能到达%s!\n",G.vexs[StartNode],G.vexs[i]);
	  getch();
	  return;
	  }
       j=i;
       PathStack[top++]=i;
       while(Path[StartNode][j]!=-1&&Path[StartNode][j]!=StartNode)
	 { PathStack[top]=Path[StartNode][j];
	   j=PathStack[top]=Path[StartNode][j];
	   top++;
           }
       
       printf("从%s到达%s的最小路径长度为:%d\n",G.vexs[StartNode],
		 G.vexs[i],dist[StartNode][i]);
       printf("路径为:%s=>",G.vexs[StartNode]);
       while(top)
	 { top--;
	   if(top>0)
	     printf("%s=>",G.vexs[PathStack[top]]);
	   else
             printf("%s",G.vexs[PathStack[top]]);
	   }
	printf("\n");
	getch();
	}
      return;
      }

 /*----------------------------------------------------*/
 /*      求一个城市到另一个城市的最短路径              */
 /*----------------------------------------------------*/
void One_To_One_Path()
{ int i,j,k,NodeNum,StartNode,EndNode;
   Mgraph G;
   //char city[CityNum][NameLenght];    //城市结点
   int dist[CityNum][CityNum];        //最短路径长度矩阵
   int Path[CityNum][CityNum];        //最短路径矩阵
   int top,PathStack[CityNum];
   char city1[NameLenght],city2[NameLenght];
   FILE *fp;

/*-----------输入城市结点数据------------*/
   if(!InputCityNode(&G)) return;

/*-----------输入最小路径数据------------*/
     if(!InputMinPath(dist,Path,&NodeNum)) return;

/*-----求一个城市到其它城市的最短路径-----*/
   printf("输入起点城市名字:");
   do{
      scanf("%s",city1);
      StartNode=search(G,city1);
      if(StartNode==-1)
	printf("起点城市名字错误，请重新输入:");
      else
	break;
      }while(1);
   printf("输入终点城市名字:");
   do{
      scanf("%s",city2);
      EndNode=search(G,city2);
      if(EndNode==-1||EndNode==StartNode)
	printf("终点城市名字错误，请重新输入:");
      else
	break;
      }while(1);
    if(dist[StartNode][EndNode]==Infinity)
      { printf("%s不能到达%s!\n",G.vexs[StartNode],G.vexs[EndNode]);
	getch();
	return;
	}
   top=0;
   j=EndNode;
   PathStack[top++]=EndNode;
   while(Path[StartNode][j]!=-1&&Path[StartNode][j]!=StartNode)
     { PathStack[top]=Path[StartNode][j];
       j=PathStack[top]=Path[StartNode][j];
       top++;
       }
   
    printf("从%s到达%s 的最小路径长度为:%d\n",G.vexs[StartNode],
	    G.vexs[EndNode],dist[StartNode][EndNode]);
    printf("路径为:%s=>",G.vexs[StartNode]);
    while(top)
      { top--;
	if(top>0)
	   printf("%s=>",G.vexs[PathStack[top]]);
	else
	   printf("%s",G.vexs[PathStack[top]]);
	}
      getch();
      return;
      }
int nemu()
{
    int num;
    printf("\n    ************* shortest path program **************\n");
    printf("    *%15c1---Calculate Shortest Path%7c\n",' ','*');
    printf("    *%15c2---One to Other Cities%11c\n",' ','*');
    printf("    *%15c3---One to Other City%13c\n",' ','*');
    printf("    *%15c4---Quit%26c\n",' ','*');
    printf("    **************************************************\n");
    printf("%15cSelcet 1,2,3,4: ",' ');
    do{
	scanf("%d",&num);
	}while(num<1 ||num>4);
    return(num);
}

void main()
{
    while(1)
    {
	switch(nemu())
	{
	    case 1:
		shorttestpath();
		break;
	    case 2:
		One_To_Other_Path();
		break;
	    case 3:
		One_To_One_Path();
		break;
	    case 4:
		return;
        }
    }
}