shortestpath.c

数据结构最短路径

                          /*计机（2）冯绍欣
                             2002374203*/


#define INFINITY 500
#define MAX 6
#define MEMBER  1
#define NONMEMBER  0
#include <stdio.h>
int G[MAX][MAX],a[MAX][MAX],route[50],certain[MAX+5];
int pd;

CreatGraph( )         /* 初始化建图 */
{ int i,j;
  for(i=0;i<MAX;i++)
     for(j=0;j<MAX;j++)
        G[i][j]=INFINITY;
  G[0][2]=G[2][0]=10;  G[0][5]=G[5][0]=100;  /* 无向图对称输入 */
  G[0][4]=G[4][0]=30;  G[1][2]=G[2][1]=5;
  G[2][3]=G[3][2]=50;  G[3][5]=G[5][3]=10;
  G[3][4]=G[4][3]=20;  G[4][5]=G[5][4]=60;
}
Shortpath (int weight[][MAX], int s, int t) /* 求两点s和t之间的最短路径 */
{ int distance[MAX],num[MAX],perm[MAX];
  int current,i,k,j,dc;
  int min, newdist;
  for(i=0;i<MAX;i++)  /* 用二维数组a来记录由s到i的最短路径 */
      { a[i][0]=s;    /* 由s到i的最短路径的起点为s，把s加入数组的第零列*/
    if(weight[s][i]<INFINITY)
       { a[i][1]=i;  /* 把跟s直接相连的点加入数组的第一列 */
         num[i]=2;   /* 一维数组num记录由s到i的最短路径的点的个数 */
       }
    else
       num[i]=1;
      }
  for (i=0;i<MAX;i++)
     { perm[i]=NONMEMBER;
       distance[i]=INFINITY;  /*先把记录最短路径的distance[i],都付给极限值*/
     }
  perm[s]=MEMBER;
  distance[s]=0;
  current=s;    /*起点作为当前点*/
  while (current!=t)
    { min=INFINITY;
      dc=distance[current];
      for (i=0;i<MAX;i++)
      if (perm[i]==NONMEMBER)
         { newdist=dc+weight[current][i];
           if (newdist<distance[i])
             { distance[i]=newdist;
               for(j=0;j<num[current];j++) /*  当前的路径较短，交换 */
               a[i][j]=a[current][j];   /*  把第current行换到第i行并把第i个点加入该行 */
               num[i]=num[current]+1;
               a[i][num[i]-1]=i;
             }
           if (distance[i]<min)
             { min=distance[i];
               k=i;
             }
         }
      current=k;
      perm[current]=MEMBER;  /* 标记已经被访问过的点 */
    }
  pd=distance[t];
  a[t][num[t]]=-1;
  if(pd>=INFINITY)   /* 表示从s到t没有路径 */
    pd=0;
}
Avoid()      /* 输入避开设定的点*/
{ int i,j,x=0;
  printf("input the avoidable nodes (end with -1 ):");
  scanf("%d",&x);   /* 输入避开点 */
  while(x!=-1)
     { for(i=0;i<MAX;i++)
         G[x][i]=G[i][x]=INFINITY;   /* 把要避开的点在矩阵中对应的行和列的值都变成无穷 */
       scanf("%d",&x);
     }
}
Certains(int s,int t)   /* 输入必经点序列，并对其进行处理 */
{ int i=1;
  certain[0]=s;              /* 把起点当成第一个必经点，放到数组的第0个位置 */
  printf("input the unavoidable nodes (end with -1 ):");
  while(certain[i-1]!=-1)
    { scanf("%d",&certain[i]);
      i++;
    }
  certain[i-1]=t;     /* 把终点当成是最后一个必经点，放到数组的最后一个 */
  certain[i]=-1;
}
Printpath()   /* 输出最短路径 */
{ int i,j,b,m=0;
  for(i=0;certain[i+1]!=-1;i++)
    { Shortpath(G,certain[i],certain[i+1]);  /* 每次求存放必经点序列数组中的第i跟第i+1个点之间的最短路径 */
      if(i==0)
        b=0;
      else
        b=1;
      if(pd!=0)                        /*  若从存放必经点序列数组中的第i到第i+1个点之间有最短路径则记录 */
          for(j=b;a[certain[i+1]][j]!=-1;j++)
           { route[m]=a[certain[i+1]][j];
             m++;
           }
      else
       { printf("No the path!\n");
         break;
       }
    }
  if(pd!=0)                          /*  若从起点到终点有最短路径则输出 */
     { printf("the shortest path from V%d to V%d  is : ",certain[0],certain[i]);
       for(i=0;i<m-1;i++)
         printf("V%d-> ",route[i]);
       printf("V%d\n",route[m-1]);
     }
}
Printmenu()
{ printf("\t\t\t\tSHORTEST PATH\n\n");
  printf("GIS:");
  printf("\t\t  <V0,V2,10>,<V2,VO,10>;  <V0,V5,100>,<V5,VO,100>\n");
  printf("\t\t  <V0,V4,30>,<V4,VO,30>;  <V1,V2,100>,<V2,V1,5>\n");
  printf("\t\t  <V2,V3,50>,<V3,V2,50>;  <V3,V5,10>,<V5,V3,10>\n");
  printf("\t\t  <V3,V4,20>,<V4,V3,20>;  <V4,V5,60>,<V5,V4,60>\n\n");
}
main()
{ int s,t;
  char z;
  clrscr();
  certain[0]=-1;
  Printmenu();
  printf("The threshold:");   /* 输入起点 */
  scanf("%d",&s);
  printf("The end  point:");          /* 输入终点 */
  scanf("%d",&t);
  CreatGraph();
  Certains(s,t);
  Avoid();
  Printpath();
  do
   { printf("\n\t\t\t\tContinue (y/n)?");
     getchar();
     z=getchar();
     clrscr();
     Printmenu();
     if(z=='y'||z=='Y')
      { printf("The threshold:");
        scanf("%d",&s);
        printf("The end  point:");
        scanf("%d",&t);
        CreatGraph();
        Certains(s,t);
        Avoid();
        Printpath();
      }
     else if(z=='n'||z=='N')
             z=-1;
          else
             printf("\nSorry, you pressed an invalid key, try again!");
    }while(z!=-1);
}