exp3.c

采用邻接矩阵实现有向网的存储

 #define INFINITY  10000
 #define NULL 0
 #define MAX_NUM   3
 void ShortestPath(int C[MAX_NUM][MAX_NUM])
 /*用Dijkstra算法求有向网C的v1定点到其余顶点v的带权路长D[v]
   final[v]为ture当且仅当v在S的集合内，就求得从v1到v的最短路径*/
 {
     int D[MAX_NUM];
     int P[MAX_NUM];
     int final[MAX_NUM];
     int S[MAX_NUM];
     int v,w,i,j,min,q,length;
     length=0;
     for(v=1;v<=MAX_NUM;v++)    /*对final[i]和D[i]初始化*/
     {
         final[v]=0;
         D[v]=C[1][v];
      }
      D[1]=0;
      final[1]=1;
      for(i=1;i<=MAX_NUM;i++)
      {
          min=INFINITY;        /*当前所知离v1顶点最近距离*/
          for(w=1;w<=MAX_NUM;w++)
          {
             if(i==w) continue;
             else if(!final[w])       /*w顶点在V-S中*/
                if(D[w]<min)           /*w顶点离v1顶点更近*/
                {
                    v=w;
                    q=w;
                    min=D[w];
                }
           }
           if(S[i+1]==0)
           S[i+1]=q;
           final[v]=1;
           for(w=0;w<=MAX_NUM;++w)      /*更新当前的最短距离*/
           {  if(i==w) continue;
              else if(!final[w]&&(min+C[v][w]<D[w]))
                D[w]=min+C[v][w];
           }
      }
    for(w=1;w<MAX_NUM;w++)       /*输出结果*/
    {   printf("%d\n",D[w]);
        length=C[S[w]][S[w+1]]+length;
        printf("The shortest path from 1 to %d is:",S[w+1]);
        for(j=1;j<=w;j++)
           printf("%d,",S[j]);
        printf(",Its length is:%d\n",length);
    }
}
 main()
 {
     int C[MAX_NUM][MAX_NUM];
     int i,j;
     for(i=1;i<=MAX_NUM;i++)
       for(j=1;j<=MAX_NUM;j++)              /*输入图的带权邻接矩阵*/
       {
           printf("Please input the Path from %d to %d:",i,j);
           scanf("%d",&C[i][j]);
       }
     ShortestPath(C);
     getch();
 }