8_5_2.c

数据结构中查询遍历算法等的实例

/* ======================================== */
/*    程式实例: 8_5_2.c                     */
/*    找寻加权图形的最短路径(Floyd方法)     */
/* ======================================== */
#define MAXLEN  1000              /* 最长可能距离         */
int cost[7][7];                   /* 图形的邻接数组       */
int dist[7][7];                   /* 最近路径长度数组     */

/* ---------------------------------------- */
/*  建立加权图形                            */
/* ---------------------------------------- */
void creategraph(int *node,int num)
{
   int from;                      /* 边线的起点           */
   int to;                        /* 边线的终点           */
   int i;

   for ( i = 0; i < num; i++ )    /* 读取边线的回路       */
   {
      from = node[i*3];           /* 边线的起点           */
      to = node[i*3+1];           /* 边线的终点           */
      cost[from][to] = node[i*3+2]; /* 存入图形           */
      cost[to][from] = node[i*3+2]; /* 存入图形           */
   }
}

/* ---------------------------------------- */
/*  找寻各顶点到各顶点的最短距离            */
/* ---------------------------------------- */
void shortestpath(int num)
{
   int i,j,k;

   for ( i = 1; i <= num; i++ )   /* 初始数组回路         */
      for ( j = 1; j <= num; j++ )
         if ( i != j )
            dist[i][j] = cost[i][j];  /* 初始距离         */
         else
            dist[i][i] = 0;       /* 清除对角线距离       */
   for ( k = 1; k <= num; k++ )   /* 找最短距离回路       */
      for ( i = 1; i <= num; i++ )
         for ( j = 1; j <= num; j++ )
            if ( dist[i][k] + dist[k][j] < dist[i][j] )
               /* 设为较短距离 */
               dist[i][j] = dist[i][k] + dist[k][j];

}

/* ---------------------------------------- */
/*  主程式: 建立图形后,从各顶点开始找寻到各 */
/*  顶点的最短距离,然后将计算结果印出.      */
/* ---------------------------------------- */
void main()
{
   int node[7][3] = {  {1, 2, 35},  /* 加权边线数组       */
                       {2, 3, 45},
                       {2, 4, 30},
                       {3, 5, 25},
                       {4, 5, 45},
                       {4, 6, 130},
                       {5, 6, 100} };
   int i,j;

   for ( i = 1; i <= 6; i++ )
      for ( j = 1; j <= 6; j++ )
         cost[i][j] = MAXLEN;     /* 设定数组最长距离     */
   creategraph(node,7);           /* 建立加权图形         */
   printf("加权图形的邻接数组内容:\n");
   for ( i = 1; i <= 6; i++ )
   {
      for ( j = 1; j <= 6; j++ )
         printf(" %4d ",cost[i][j]);  /* 印出加权数组内容 */
      printf("\n");                   /* 换行             */
   }
   shortestpath(6);                   /* 找寻最短路径     */
   printf("\n从各顶点到各顶点最近距离:\n");
   printf("顶点1     2     3     4     5     6\n");
   for ( i = 1; i <= 6; i++ )
   {
      for ( j = 1; j <= 6; j++ )
         printf(" %4d ",dist[i][j]);  /* 印出最短距离数组 */
      printf("\n");                   /* 换行             */
   }
}