狄克斯特拉算法

  1. #include <stdio.h>
  2. #define MAXVEX 100
  3. #define INF 32767
  5. void Dijkstra(int cost[][MAXVEX],int n,int v)
  6. {
  7.     int dist[MAXVEX],path[MAXVEX];
  8.     int s[MAXVEX];
  9.     int mindis,i,j,u,pre;
  10.     for (i=0;i<n;i++) 
  11.     {    
  12.         dist[i]=cost[v][i];           /*距离初始化*/
  13.         s[i]=0;                        /*s[]置空*/
  14.         if (cost[v][i]<INF)            /*路径初始化*/
  15.             path[i]=v;
  16.         else
  17.             path[i]=-1;
  18.     }
  19.     s[v]=1;path[v]=0;                /*源点编号v放入s中*/
  20.     for (i=0;i<n;i++)                 /*循环直到所有顶点的最短路径都求出*/
  21.     {    
  22.         mindis=INF;
  23.         u=-1;
  24.         for (j=0;j<n;j++)             /*选取不在s中且具有最小距离的顶点u*/
  25.             if (s[j]==0 && dist[j]<mindis) 
  26.             {     
  27.                 u=j;
  28.                 mindis=dist[j];    
  29.             }
  30.         if (u!=-1)                        /*找到最小距离的顶点u*/
  31.         {    s[u]=1;                     /*顶点u加入s中*/
  32.             for (j=0;j<n;j++)              /*修改不在s中的顶点的距离*/
  33.                 if (s[j]==0) 
  34.                     if (cost[u][j]<INF && dist[u]+cost[u][j]<dist[j]) 
  35.                     {    
  36.                         dist[j]=dist[u]+cost[u][j];
  37.                         path[j]=u;
  38.                     } 
  39.         }
  40.     }
  41.     printf("\n Dijkstra算法求解如下:\n"); 
  42.     for (i=0;i<n;i++)                /*输出最短路径长度,路径逆序输出*/
  43.     {
  44.         if (i!=v)
  45.         {    
  46.             printf("  %d->%d:",v,i);
  47.             if (s[i]==1)  
  48.             {    
  49.                 printf("路径长度为%2d ",dist[i]);
  50.                 pre=i;
  51.                 printf("路径逆序为");
  52.                 while (pre!=v)        /*一直求解到初始顶点*/
  53.                 {    
  54.                     printf("%d,",pre);
  55.                     pre=path[pre];
  56.                 }
  57.                 printf("%d\n",pre);
  58.             }
  59.             else
  60.                 printf("不存在路径\n");
  61.         }
  62.     }
  63. }
  65. void main()
  66. {
  67.     int cost[6][MAXVEX]={        /*图6.9的代价矩阵*/
  68.         {0,50,10,INF,INF,INF},
  69.         {INF,0,15,50,10,INF},
  70.         {20,INF,0,15,INF,INF},
  71.         {INF,20,INF,0,35,INF},
  72.         {INF,INF,INF,30,0,INF},
  73.         {INF,INF,INF,3,INF,0}};
  74.     Dijkstra(cost,6,1);
  75.     printf("\n");
  76. }