1. #include "stdio.h"    
    2. #include "stdlib.h"   
    3. #include "io.h"  
    4. #include "math.h"  
    5. #include "time.h"
    7. #define OK 1
    8. #define ERROR 0
    9. #define TRUE 1
    10. #define FALSE 0
    12. #define MAXEDGE 20
    13. #define MAXVEX 20
    14. #define INFINITY 65535
    16. typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 
    19. typedef struct
    20. {
    21.     int vexs[MAXVEX];
    22.     int arc[MAXVEX][MAXVEX];
    23.     int numVertexes, numEdges;
    24. }MGraph;
    26. typedef int Patharc[MAXVEX];    /* 用于存储最短路径下标的数组 */
    27. typedef int ShortPathTable[MAXVEX];/* 用于存储到各点最短路径的权值和 */
    29. /* 构件图 */
    30. void CreateMGraph(MGraph *G)
    31. {
    32.     int i, j;
    34.     /* printf("请输入边数和顶点数:"); */
    35.     G->numEdges=16;
    36.     G->numVertexes=9;
    38.     for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    39.     {
    40.         G->vexs[i]=i;
    41.     }
    43.     for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    44.     {
    45.         for ( j = 0; j < G->numVertexes; j++)
    46.         {
    47.             if (i==j)
    48.                 G->arc[i][j]=0;
    49.             else
    50.                 G->arc[i][j] = G->arc[j][i] = INFINITY;
    51.         }
    52.     }
    54.     G->arc[0][1]=1;
    55.     G->arc[0][2]=5; 
    56.     G->arc[1][2]=3; 
    57.     G->arc[1][3]=7; 
    58.     G->arc[1][4]=5; 
    60.     G->arc[2][4]=1; 
    61.     G->arc[2][5]=7; 
    62.     G->arc[3][4]=2; 
    63.     G->arc[3][6]=3; 
    64.     G->arc[4][5]=3;
    66.     G->arc[4][6]=6;
    67.     G->arc[4][7]=9; 
    68.     G->arc[5][7]=5; 
    69.     G->arc[6][7]=2; 
    70.     G->arc[6][8]=7;
    72.     G->arc[7][8]=4;
    75.     for(i = 0; i < G->numVertexes; i++)
    76.     {
    77.         for(j = i; j < G->numVertexes; j++)
    78.         {
    79.             G->arc[j][i] =G->arc[i][j];
    80.         }
    81.     }
    83. }
    85. /*  Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */    
    86. /*  P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */  
    87. void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
    88. {    
    89.     int v,w,k,min;    
    90.     int final[MAXVEX];/* final[w]=1表示求得顶点v0至vw的最短路径 */
    91.     for(v=0; v<G.numVertexes; v++)    /* 初始化数据 */
    92.     {        
    93.         final[v] = 0;            /* 全部顶点初始化为未知最短路径状态 */
    94.         (*D)[v] = G.arc[v0][v];/* 将与v0点有连线的顶点加上权值 */
    95.         (*P)[v] = -1;                /* 初始化路径数组P为-1  */       
    96.     }
    98.     (*D)[v0] = 0;  /* v0至v0路径为0 */  
    99.     final[v0] = 1;    /* v0至v0不需要求路径 */        
    100.     /* 开始主循环，每次求得v0到某个v顶点的最短路径 */   
    101.     for(v=1; v<G.numVertexes; v++)   
    102.     {
    103.         min=INFINITY;    /* 当前所知离v0顶点的最近距离 */        
    104.         for(w=0; w<G.numVertexes; w++) /* 寻找离v0最近的顶点 */    
    105.         {            
    106.             if(!final[w] && (*D)[w]<min)             
    107.             {                   
    108.                 k=w;                    
    109.                 min = (*D)[w];    /* w顶点离v0顶点更近 */            
    110.             }        
    111.         }        
    112.         final[k] = 1;    /* 将目前找到的最近的顶点置为1 */
    113.         for(w=0; w<G.numVertexes; w++) /* 修正当前最短路径及距离 */
    114.         {
    115.             /* 如果经过v顶点的路径比现在这条路径的长度短的话 */
    116.             if(!final[w] && (min+G.arc[k][w]<(*D)[w]))   
    117.             { /*  说明找到了更短的路径，修改D[w]和P[w] */
    118.                 (*D)[w] = min + G.arc[k][w];  /* 修改当前路径长度 */               
    119.                 (*P)[w]=k;        
    120.             }       
    121.         }   
    122.     }
    123. }
    125. int main(void)
    126. {   
    127.     int i,j,v0;
    128.     MGraph G;    
    129.     Patharc P;    
    130.     ShortPathTable D; /* 求某点到其余各点的最短路径 */   
    131.     v0=0;
    133.     CreateMGraph(&G);
    135.     ShortestPath_Dijkstra(G, v0, &P, &D);  
    137.     printf("最短路径倒序如下:\n");    
    138.     for(i=1;i<G.numVertexes;++i)   
    139.     {       
    140.         printf("v%d - v%d : ",v0,i);
    141.         j=i;
    142.         while(P[j]!=-1)
    143.         {
    144.             printf("%d ",P[j]);
    145.             j=P[j];
    146.         }
    147.         printf("\n");
    148.     }    
    149.     printf("\n源点到各顶点的最短路径长度为:\n");  
    150.     for(i=1;i<G.numVertexes;++i)        
    151.         printf("v%d - v%d : %d \n",G.vexs[0],G.vexs[i],D[i]);     
    152.     return 0;
    153. }