• 狄克斯特拉算法

    狄克斯特拉算法

    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. }